[Python][백준 1194][BFS][bit masking] 달이 차오른다, 가자. - 컴도리돌이
풀이과정 해당 문제는 방문 표시만 제대로 하면 쉽게 해결할 수 있는 문제이다. 물론 방문 표시가 생각보다 까다롭다. 😂 시작점에서 끝점까지 도달하는 최단 거리는 너비 우선 탐색(BFS)으로 구현하면 된다. 그렇다면 이 문제의 핵심은 방문 표시이다. 탈출을 하기 위해서는 '.' 공간만 이용할 수 있다. 물론 주어진 n*m 행렬 맵에서는 키라는 특이한 요소를 첨가했다. 키의 종류는 a, b, c, d, e, f 총 6가지이며, 키의 종류 따른 문의 종류도 A, B, C, D, E, F 총 6가지이다. 문제에서는 탈출구까지 가는 길에 문이 있으면 해당 문에 맞는 키 값을 소유하고 있어야 한다. 그렇기 때문에 BFS 탐색할 때 방문 표시를 가지고 있는 키 값들에 따라 해주어야 한다. 키의 종류는 총 6가지이다...
더보기
