191004 백준 알고리즘 문제풀기

|

[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. 현재 위치에서 현재 방향 기준으로 왼쪽부터 탐색한다.
      • 현재 위치에서 왼쪽이 청소되지 않았다면, 그 방향으로 회전 후 이동 후 청소한다(1번)
      • 왼쪽이 청소되어있거나 벽이라면, 해당 방향으로 회전만 한다. 그리고 다시 2번으로 돌아간다.
      • 네 방향 모두 청소가 되어있거나 벽이라면, 우선 바라보는 방향을 유지한 채 한 칸 후진 후 2번으로 돌아간다.
      • 네 방향 모두 청소가 되어있거나 벽이고, 후진 불가능하다면 작동을 멈춘다.
#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;
}