[SWEA] 1953. 탈주범 검거

문체 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

SW Expert Academy

 2019년 12월 28일 2시에 2문제 풀기를 시작해 성공했습니다. 이번 문제는 1시간 17분 다음 문제는 1시간안에 풀 수 있었습니다. 생각보다 운이 많이 따라줘서 시간안에 풀 수 있었던 것 같습니다.  

 

 이번 문제는 흉악범을 교도소로 이송시키는 도중에 흉악범이 탈출하여 수색에 나섰는데 멘홀 뚜껑을 통해 달아난 흉악범이 있을 수 있는 위치의 개수를 계산하는 문제입니다. 문제를 읽어보시면 알겠지만 bfs로 푸는 문제입니다. 쉬운 문제라고 생각했다가 된통 당했습니다. 알고리즘 자체는 어렵지 않았으나 따져야 할게 많아서 구현하는게 조금 까다로웠습니다. 

 

 이번 문제의 포인트는 각 터널모양에 맞게 탐색을 해주어야 합니다. 먼저, 현재에 있는 터널이 어느 방향으로 이동 가능한지 구별 해야합니다. 예를 들어, 4번 터널의 경우에는 위나 오른쪽으로만 이동이 가능합니다. 다른 방향으로는 이동할 수 없으므로 다른 방향은 탐색하면 안됩니다.(75 ~ 95라인) 또, 이동한 방향에 있는 터널과 연결이 되어있는지 여부를 따져봐야합니다. 예를 들어 현재의 위치에 있는 터널이 4번 터널인데 오른쪽으로 이동하려고 합니다. 하지만 만약 현재 위치의 오른쪽에 있는 터널이 2번 터널이면 두 터널은 연결이 되어있지 않으므로 2번 터널이 있는 위치는 탐색할 수가 없습니다. 이 두가지를 모두 만족시켜야만 탐색이 가능합니다.(22~ 52라인)