191004 백준 알고리즘 문제풀기
04 Oct 2019 | baekjoon[17144] 미세먼지 안녕!
- 난이도: 중
- 풀이는 금방 떠올랐으나, 실수로 인해 구현에 시간이 오래걸렸다.
- 완전 탐색이 필요한 경우 큐를 사용하면 되지만, 이 문제는 초 단위로 먼지의 이동과 공기청정기의 바람부는 연산으로 1초 연산으로 나뉜다.
- 따라서 BFS를 사용하면 더 복잡할 것 같아 일반 for문으로 문제를 풀었다.
- 문제
- https://www.acmicpc.net/problem/17144
- 가로, 세로 길이 각각 c, r인 맵과 시간 t, 그리고 해당 맵에 입력으로 주어졌을 때, t초 후 공간에 존재하는 먼지들의 합을 구한다.
- 1초 단위로 구동되며 1초동안 아래의 연산이 수행됨
- 미세먼지의 확산(모든 칸에서 동시에)
- (r, c)에 있는 미세먼지는 상하좌우로 확산
- 상하좌우에 공기청정기가 있거나, 칸이 없으면 확산 발생하지 않음
- 만약 칸에 미세먼지가 5보다 작게 존재할 경우, 미세먼지는 줄어들지 않는다!
- 확산되는 양은 해당 칸의 먼지/5 이며, 소수점은 버림
- 해당 칸에 남은 미세먼지 양은 사라진 양 만큼임
- 해당 칸 처음 먼지량 - 해당 칸 먼지/5 * 퍼진 칸 수
- 공기청정기의 작동
- 바람이 나와 위로는 반시계, 아래로는 시계방향으로 바람이 돈다.
- 바람 불면 미세먼지가 한 칸씩 이동
- 공기청정기의 바람은 먼지가 하나도 없음(들어간 먼지는 모두 정화)
- 미세먼지의 확산(모든 칸에서 동시에)
- 입력
- 첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.
- 둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.
- 풀이
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int map[50][50]; // 현재 상황용 맵
int check[50][50]; // 먼지가 퍼지고 난 후의 맵
int dx[] = { -1,1,0,0 }; // 이동 방향 정의
int dy[] = { 0,0,-1,1 };
void spread(int w, int h) // 먼지 퍼치기
{
for (int y = 0; y < h; y++)
{
for (int x = 0; x < w; x++)
{
if (check[y][x] > 4)
{ // 전체 맵에 대해 해당 칸에 먼지가 4 초과 존재 할 경우
int cx = x; // 현재 칸 정의
int cy = y;
int cnt = 0; // 퍼진 양 계산용 카운팅
int d = map[cy][cx] / 5; // 퍼지는 미세먼지 양(먼지 퍼지기 전에서 계산)
for (int i = 0; i < 4; i++)
{
int nx = cx + dx[i]; // 다음 칸 정의
int ny = cy + dy[i];
if (0 <= nx && nx < w && 0 <= ny && ny < h && check[ny][nx] != -1) // 다음 칸이 범위 안이고, 공기청정기가 아닌 경우
{
check[ny][nx] += d; // 먼지가 퍼진다.
cnt++; // 퍼진 양 카운팅
}
}
int nd = map[cy][cx] / 5 * cnt; // 퍼진 먼지 양 계산
check[cy][cx] -= nd; // 현재 칸에 퍼진 먼지 양 만큼 빼줌
}
}
}
}
void wind(int ay, int w, int h) // 바람
{
int uy = ay - 1;
int ly = ay;
int br, tr, tl, bl;
// 윗부분 움직이기
br = check[uy][w - 1];
tr = check[0][w - 1];
tl = check[0][0];
bl = check[uy][0];
//방향 1: y = uy
for (int i = w - 1; i > 0; i--)
{
check[uy][i] = check[uy][i - 1];
}
check[uy][0] = -1;
check[uy][1] = 0;
//방향 2: x=7
for (int j = 0; j < uy; j++)
{
if (j + 1 == uy)
{
check[j][w - 1] = br;
}
else
{
check[j][w - 1] = check[j + 1][w - 1];
}
}
//방향 3: y=0
for (int i = 0; i < w - 1; i++)
{
if (i + 1 == w - 1)
{
check[0][i] = tr;
}
else
{
check[0][i] = check[0][i + 1];
}
}
//방향 4: x=0
for (int j = uy; j > 0; j--)
{
if (j - 1 == 0)
{
check[j][0] = tl;
}
else
{
check[j][0] = check[j - 1][0];
}
}
check[uy][0] = -1;
// 아랫부분 움직이기
br = check[h - 1][w - 1];
tr = check[ly][w - 1];
tl = check[ly][0];
bl = check[h - 1][0];
//방향 1: y=ly
for (int i = w - 1; i > 0; i--)
{
check[ly][i] = check[ly][i - 1];
}
check[ly][0] = -1;
check[ly][1] = 0;
//방향 2: x=w-1
for (int j = h - 1; j > ly; j--)
{
if (j - 1 == ly)
{
check[j][w - 1] = tr;
}
else
{
check[j][w - 1] = check[j - 1][w - 1];
}
}
//방향 3: y=h-1
for (int i = 0; i < w - 1; i++)
{
if (i + 1 == w - 1)
{
check[h - 1][i] = br;
}
else
{
check[h - 1][i] = check[h - 1][i + 1];
}
}
//방향 4: x=0
for (int j = ly; j < h - 1; j++)
{
if (j + 1 == h - 1)
{
check[j][0] = bl;
}
else
{
check[j][0] = check[j + 1][0];
}
}
check[ly][0] = -1;
}
int summation(int w, int h) // 합 계산용
{
int result = 2; // 공기청정기 2칸이 각각 -1이므로 2로 초기화
for (int j = 0; j < h; j++)
{
for (int i = 0; i < w; i++)
{
result += check[j][i];
}
}
return result;
}
int main()
{
int r, c, t; // r: 세로길이, c: 가로길이, t: test case
scanf("%d %d %d", &r, &c, &t);
int ax, ay;
for (int j = 0; j < r; j++)
{
for (int i = 0; i < c; i++)
{
scanf("%d", &map[j][i]);
if (map[j][i] == -1)
{
ax = i;
ay = j;
}
if (map[j][i] != 0)
{
check[j][i] = map[j][i];
}
}
}
while (t--)
{
spread(c, r);
wind(ay, c, r);
for (int j = 0; j < r; j++)
{
for (int i = 0; i < c; i++)
{
map[j][i] = check[j][i]; // 먼지 퍼진 맵을 현재 맵으로 초기화한다.(그래야 다음 t때 퍼지는 먼지 사용)
}
}
}
int answer = summation(c, r);
printf("%d\n", answer);
//system("pause");
return 0;
}
[14503] 로봇 청소기
- 난이도: 상
- 풀이를 떠올렸지만 조건이 많아 구현하는데 애먹었다.
- 특히 짜증났던게, 조건이 명확하지 않고 애매하게 표현된다.
- 왼쪽으로 뱅글뱅글 돌아가며 찾아야 한다.
- 문제
- https://www.acmicpc.net/problem/14503
- 현재 위치를 청소한다
- 현재 위치에서 현재 방향 기준으로 왼쪽부터 탐색한다.
- 현재 위치에서 왼쪽이 청소되지 않았다면, 그 방향으로 회전 후 이동 후 청소한다(1번)
- 왼쪽이 청소되어있거나 벽이라면, 해당 방향으로 회전만 한다. 그리고 다시 2번으로 돌아간다.
- 네 방향 모두 청소가 되어있거나 벽이라면, 우선 바라보는 방향을 유지한 채 한 칸 후진 후 2번으로 돌아간다.
- 네 방향 모두 청소가 되어있거나 벽이고, 후진 불가능하다면 작동을 멈춘다.
- https://www.acmicpc.net/problem/14503
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <tuple>
#include <queue>
using namespace std;
int map[50][50];
int check[50][50];
int answer = 0;
int dx[] = { 0,1,0,-1 }; // 순서대로 청소기의 방향을 0,1,2,3으로 정함
int dy[] = { -1,0,1,0 };
int left(int n)
{ // 좌회전
if (n == 3) return 2;
if (n == 2) return 1;
if (n == 1) return 0;
else return 3;
}
int right(int n)
{ // 우회전
if (n == 3) return 0;
if (n == 2) return 3;
if (n == 1) return 2;
else return 1;
}
int back(int n)
{ // 뒤돌기
if (n == 3) return 1;
if (n == 2) return 0;
if (n == 1) return 3;
else return 2;
}
void clean(int x, int y, int d, int w, int h)
{ // 청소
// 변수선언 및 현재위치 초기화
int cx, cy, cd;
int nx, ny, nd;
cx = x;
cy = y;
cd = d;
while (1)
{
if (map[cy][cx] == 0 && check[cy][cx] == 0)
{ // 현재 위치에 벽이 없고 청소되어있지 않다면 청소한다.
answer++;
check[cy][cx] = answer;
}
//왼쪽 탐색
nd = left(cd); // 현재 방향에서 왼쪽으로 돌고 다음 방향을 정의
nx = cx + dx[nd];
ny = cy + dy[nd];
if (map[ny][nx] == 0 && check[ny][nx] == 0)
{ // 만약 다음 방향이 벽이 아니고 청소하지 않았다면
cd = nd; //회전한 방향을 현재 방향으로 초기화 하고 continue
cy = ny;
cx = nx;
continue;
}
else
{ // 다음 방향이 청소 불가능하다면
int turn_cnt = 0;
while (check[ny][nx] != 0)
{ // 다음 청소할곳 찾을때까지 왼쪽으로 회전
nd = left(nd);
nx = cx + dx[nd];
ny = cy + dy[nd];
turn_cnt++;
if (turn_cnt == 4) break; // 한 바퀴 돌았는데도 못찾았으면 빠져 나온 후 if문 이동
}
if (turn_cnt == 4)
{ // 네 방향 모두 청소가 이미 되어있거나 벽이라면
nd = back(cd); //후진방향
nx = cx + dx[nd]; // 후진 좌표 설정
ny = cy + dy[nd];
if (map[ny][nx] == 1)
{ // 만약 후진 방향이 벽이라면
break; // 종료
}
cx = nx; // 현재 위치를 후진 위치로 초기화
cy = ny;
//cd는 원래 방향이 그대로 유지되어야 하므로 별도 초기화가 필요 없음
continue;
}
else
{ // 만약 한 바퀴 돌기 전에 다음 청소할 곳 찾았으면
cd = right(nd); // while문 시작부분 check 후 왼쪽 탐색 조건을 만족시키기 위해 오른쪽을 다시 바라보게 해야 한다.
}
}
}
}
int main()
{
int N, M; // N: H, M: W
scanf("%d %d", &N, &M);
int r, c, d; // r: y, c: x
scanf("%d %d %d", &r, &c, &d);
for (int j = 0; j < N; j++)
{
for (int i = 0; i < M; i++)
{
scanf("%d", &map[j][i]);
if (map[j][i] == 1)
{
check[j][i] = -1;
}
}
}
clean(c, r, d, M, N);
printf("%d\n", answer);
//system("pause");
return 0;
}