[알고리즘 문제 풀이][시뮬레이션] 백준 1194번 - 달이 차오른다, 가자.

백준 1194번 달이 차오른다, 가자. 문제입니다.

(삼성 SW 코딩 테스트 유형 - BFS)

 

- 문제 설명: https://www.acmicpc.net/problem/1194

- 문제 풀이:

 

미로의 출발점 (0) 에서 도착점 (1) 까지 최단 거리를 구하는 문제입니다. 벽 (#) 으로 막힌 곳은 지나갈 수 없습니다. 이 문제에서 가장 중요한 것은 열쇠 (a ~ f) 를 먹어야만 문 (A ~ F) 를 열 수 있다는 것입니다. 아래의 예시를 보면 출발점 (0) 부터 시작해서 a 열쇠를 먹고 A 문을 연 후에 c 열쇠를 먹고 C 문을 열어야 도착점 (1) 로 갈 수 있습니다.

 

※ 풀이시 주의해야할 점은 도착점 (1) 이 단 하나만 존재하는 것이 아닙니다. 여러곳이 존재하는데 그 중 가장 빨리 도착하는 곳을 찾으면 됩니다.

8 6
######
#0...#
####.#
#....A
a.###.
#.###.
#C#.#.
#1###c
Answer: 32

 

최단 거리이므로 BFS 로 문제를 풀면 될 것 같은데, 문제는 visited 배열을 단순히 x, y 좌표의 2차원으로 구성하면 열쇠를 먹은 후에 visited 체크가 되어서 돌아올 수가 없는 것입니다. 열쇠를 먹은 상태 또한 visited에 저장이 되어야하며, 6개의 열쇠를 먹으면서 생기는 다양한 조합을 다 커버할 수 있어야합니다. 그래서 대부분 이 문제를 풀 때 BFS 로 풀고, visited 배열의 세번째 차원을 비트마스크를 이용하여 열쇠 상태를 표시하게 됩니다.

 

열쇠를 먹지 않았는지 (False) 먹었는지 (True) 이 2가지 상태만 표현하면 되기 때문에 1 bit 에 1개의 열쇠 상태를 표현할 수 있습니다.

 

6개의 열쇠는 6 bit 가 있으면 되고, 2**6 = 64 크기가 필요합니다.

따라서 visited 배열은 visited[50][50][64] 이런 형태가 됩니다. (map 의 최대 크기가 50 x 50)

 

- 코드: 

from collections import deque
import sys
input = sys.stdin.readline

def set_key(key, index):
    return key | (1 << index)

def check_door(key, index):
    return (1 << index) & key

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

N, M = map(int, input().split())
miro = [input() for _ in range(N)]

# find start point
def find_start():
    for i in range(N):
        for j in range(M):
            if miro[i][j] == '0':
                return i, j

sx, sy = find_start()

visited = [[[0]*(1<<6) for _ in range(M)] for __ in range(N)]
que = deque() # x,y,dist,keys

que.append([sx, sy, 0, 0])
visited[sx][sy][0] = 1

def bfs():
    while que:
        x, y, dist, key = que.popleft()

        for d in range(4):
            nkey = key
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < N and 0 <= ny < M and miro[nx][ny] != '#' and not visited[nx][ny][key]:
                np = ord(miro[nx][ny])
                if miro[nx][ny] == '1':
                    return dist+1
                elif 65 <= np <= 70 and not check_door(key, np - 65): # ord('F'), ord('A')
                        continue
                elif 97 <= np <= 102: # ord('f') ord('a')
                        nkey = set_key(key, np - 97)
                que.append([nx, ny, dist + 1, nkey])
                visited[nx][ny][nkey] = 1
    else:
        return -1

print(bfs())

위에서 설명한 비트마스크 부분은 set_key 함수와 check_door 함수를 참고해주시면 됩니다.

 

그런데 제가 작성한 코드는 아니지만 비트마스크를 이용하지 않은 버전의 코드도 있어 공유드립니다.

(출처: https://www.acmicpc.net/board/view/14074)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int r = 0;
int c= 0;
int visit[100][100];
char arr[100][100];
int curKey[1000000][255];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int aQue = 0;
int bQue = 0;
int minRsult = 1000000;
int flag = 0;


int QueX[1000000];
int QueY[1000000];
int QueL[1000000];
int sQueX[1000000];
int sQueY[1000000];
int sQueL[1000000];
void init();
void push(int a, int b, int c);
void spush(int a, int b, int c, int count, char key);
void Input();
void Bfs(int cnt);

int main()
{
	int i = 0;
	Input();
	while (i < bQue)
	{
		Bfs(i);
		if (flag == 1)
		{
			return 0;
		}
		init();
		i++;
	}
	printf("-1\n");
	return 0;
}

void push(int a,int b,int c)
{
	QueX[aQue] = a;
	QueY[aQue] = b;
	QueL[aQue] = c;
	aQue++;
}
void spush(int a, int b, int c, int count, char key)
{
	sQueX[bQue] = a;
	sQueY[bQue] = b;
	sQueL[bQue] = c;
	if (bQue != 0)
	{
		memcpy(curKey[bQue], curKey[count], sizeof(curKey[bQue]));
	}
	if (key != 0)
	{
		curKey[bQue][key - 32] = 1;
	}
	bQue++;
}

void Input()
{
	int i = 0;
	int k = 0;
	scanf("%d %d", &r, &c);
	for (i = 0; i < r; i++)
	{
		scanf("%s", arr[i]);
	}
	for (i = 0; i < r; i++)
	{
		for (k = 0; k < c; k++)
		{
			if (arr[i][k] == '0')
			{
				visit[i][k] = 1;
				arr[i][k] = '.';
				spush(i, k, 0, 0, 0);
			}
		}
	}

}

void Bfs(int cnt)
{
	int i = 0;
	int rx = 0;
	int ry = 0;
	int count = 0;
	push(sQueX[cnt], sQueY[cnt], sQueL[cnt]);
	visit[sQueX[cnt]][sQueY[cnt]] = 1;
	while (count < aQue)
	{
		if (arr[QueX[count]][QueY[count]] == '1')
		{
			if (minRsult > QueL[count])
			{
				minRsult = QueL[count];
				flag = 1;
				printf("%d\n", minRsult);
				//return;
			}
		}
		for (i = 0; i < 4; i++)
		{
			rx = QueX[count] + dx[i];
			ry = QueY[count] + dy[i];
			if (rx<r && ry <c && rx>-1 && ry >-1 && visit[rx][ry] == 0)
			{
				if (arr[rx][ry] != '#')
				{
					if (arr[rx][ry] == '.' || arr[rx][ry] == '1')
					{
						visit[rx][ry] = 1;
						push(rx, ry, QueL[count] + 1);
					}
					else if (arr[rx][ry] >= 'a' && arr[rx][ry] <= 'f')
					{
						if (curKey[cnt][arr[rx][ry] - 32] != 1)
						{
							spush(rx, ry, QueL[count] + 1, cnt, arr[rx][ry]);
							visit[rx][ry] = 1;
						}
						else
						{
							visit[rx][ry] = 1;
							push(rx, ry, QueL[count] + 1);
						}

					}
					else if (arr[rx][ry] >= 'A'&& arr[rx][ry] <= 'F')
					{
						if (curKey[cnt][arr[rx][ry]] == 1)
						{
							visit[rx][ry] = 1;
							push(rx, ry, QueL[count] + 1);
						}
						else
						{

						}
					}
				}
			}

		}
		count++;

	}

}

void init()
{

	memset(visit, 0, sizeof(visit));
	memset(QueX, 0, sizeof(QueX));
	memset(QueY, 0, sizeof(QueY));
	memset(QueL, 0, sizeof(QueL));
	aQue = 0;
}

큐를 상위의 큐와 하위의 큐로 나누어서, 열쇠를 먹으면 거기부터 다시 돌 수 있도록 상위의 큐에 열쇠와 시작점을 전달하는 코드입니다.

 

- 실수 포인트 & 반례:

1. 런타임 에러

- BFS 를 푸는 경우 많은 경우 런타임 에러를 만날 수 있는데, 큐 사이즈를 너무 작게 잡았거나, visited 체크를 제대로 하지 않아서 큐에 끊임없이 들어가는 경우가 가능합니다. 위의 문제에서는 50 x 50 x (2^6) = 160,000 크기 이상을 잡아야합니다.

- 큐 종료 조건을 qe > qs 로 해야하는데, qe >= qs 로 한 경우에도 런타임 에러가 발생하였습니다. 이때도 역시 제때 종료되지 않고 큐에 새로운 값이 계속 들어가서 큐가 폭발한 것으로 추정됩니다.

 

2. 시간 초과

- 본 문제를 DFS 로 풀이하는 경우, 시간 초과가 날 수 있습니다. DFS는 가능한 모든 지점을 다 돌기 때문에 최단 거리를 구하는 문제에는 대부분 적합하지 않습니다.

 

BFS와 DFS 의 차이: https://haams704.tistory.com/75

BFS는 너비우선탐색으로 현재 나의 위치에서 가장 가까운 노드를 먼저 방문하는 것이다.
방문하면서 현재 위치는 pop해주고 방문한 곳은 체크한 뒤, 방문할 곳은 큐에 넣는 과정입니다.
따라서, 미로 탐색과 같은 알고리즘은 최단 거리만을 가지고 탈출하는 것이기에 BFS가 적합합니다.

하지만 가령, 미로탐색을 진행하는데, 이동할 때마다 가중치가 붙어서 이동한다거나, 이동 과정에서 
여러 제약이 있을 경우, DFS로 구현하는 것이 좋습니다.
탐색 시간은 더 걸리긴 하지만, 가중치에 대한 변수를 지속해서 관리할 수 있다는 장점이 있으므로 
코드 구현 시, 더 편리하기 때문입니다.

- 시간 초과 확인에 좋은 반례는 다음과 같습니다.

https://www.acmicpc.net/board/view/32615

8 6
abcdef
......
......
.....0
#####.
ABCDEF
.#####
.....1
Answer: 30

- 다양한 반례 모음

https://www.acmicpc.net/board/view/67310

https://www.acmicpc.net/board/view/35648

https://www.acmicpc.net/board/view/32615

https://www.acmicpc.net/board/view/23445

 

3. 틀렸습니다

- 본 문제는 도착점 (1) 이 여러 곳일 수 있음에도 불구하고 문제 출제 초반에는 도착점이 한 곳이라고 잘못 표기되어서 틀렸습니다는 받은 분들이 많았습니다. 도착점이 여러 곳이라는 것을 감안하고 풀이해야합니다.

 

- 최적화 시도:

아래와 같은 실행 시간에 대해 최적화 시도를 하였으며, 결과는 다음과 같습니다.

파이썬 실행 시간이 일정하지 않은 것인지 오차가 큰 것으로 보입니다.

 

(1) bfs 를 함수화하여 도착점에 도달하는 경우 즉시 return 하도록 하여 쓸데없는 코드 실행을 막아 시간 단축: 444ms -> 368 ms
(2) ord() 함수를 사용하지 않고 아스키값 숫자로 변경: 368 ms -> 348 ms
(3) x => 0 and x <= r 같은 형식 말고 0 <= x <= r 로 변경: 348 ms -> 308 ms
(3) 반복된 변수 줄이기 x + dx[d] 를 nx로, y + dy[d] 를 ny 로 변경: 308 ms -> 272 ms
(4) 반복된 변수 줄이기 ord(miro[nx][ny]) 를 np 변수로, ord('A') 를 아스키값 숫자로 변경하지 않은 거 1개 남아있어서 마저 변경: 272 ms -> 296 ms

(5) 불필요한 if 문 줄이고 다 and 로 조건 연결: 296 ms -> 276 ms

(6) 출발점 찾는 것도 find_start로 함수화하여 0 찾자마자 return으로 즉시 종료하도록 변경: 276 ms -> 360 ms 
(7) 파이썬은 메모리 할당시 힙으로 하기 때문에 너무 큰 정적 배열은 오히려 속도 저하를 일으킬 수 있다. queue 사이즈를 200,000 에서 queue.append 로 변경: 360 ms -> 164 ms
(8) 위와 같은 이유로 배열을 크게 만들면 상당한 시간이 소요되는 것 같아서 1<<7 사이즈에서 최소한으로 필요한 1<<6으로 변경: 164 ms -> 148 ms
(9) input 배열 받을 때 [0] 으로 초기화시켜둔 것을 input 받은 문자열로 바꾸는데 시간이 소요될까 싶어서 input() 을 아예 list 로 받도록 수정: 148 ms -> 160 ms
(10) list인 q.pop(0) 을 deque로 바꿔서 q.popleft()로 변경: 160 ms -> 188 ms

deque 속도 실험 결과: https://velog.io/@dramatic/Python-Deque
(11) stdin.readline으로 input 읽기: 188 ms -> 200 ms