너비우선탐색

풀이 과정 본 문제는 전형적인 BFS문제이다. 왜냐하면 연결되어 있는 방의 개수를 물어봤기 때문이다. 부가적으로 특이한 요소를 첨가하였다. 각 좌표들 간에 연결되었는지를 15 이하의 값으로 주어져있다. 0~15 (?) 문제에서 언급한 힌트대로 이 문제는 좌표 이동을 비트 마스킹을 해준다. 하지만 비트 마스킹이 익숙하지 않아서,,, 나는 문자열로 표시를 하였다. 물론 하는 방법은 비트 마스킹이랑 똑같다..! "0000" ~ "1111" 맨 왼쪽부터 서북 동남을 의미하고 1은 이동 불가(벽으로 연결)를 의미하고 0은 이동 가능을 의미한다. 1. m*n 만큼 반복문을 돌려서 해당 (i, j) 위치를 방문하지 않을 경우 BFS 탐색을 한다. 2. 현재 위치 값을 bin함수를 이용하여 이진수를 나타내고 크기를 4..

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