[BOJ] #17090 미로 탈출하기

시간 제한	메모리 제한	정답 비율
1초	512MB	30.346%

17090번: 미로 탈출하기

 

문제

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다.

어떤 칸(r, c)에 적힌 문자가

• U인 경우에는 (r-1, c)로 이동해야 한다.
• R인 경우에는 (r, c+1)로 이동해야 한다.
• D인 경우에는 (r+1, c)로 이동해야 한다.
• L인 경우에는 (r, c-1)로 이동해야 한다.

미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

 

해결

key point, chk배열의 값이 0이면 탐색 가능, -1이면 탐색중, 1이면 탈출 가능, 2이면 탈출 불가능

• 한 번 탐색한 경로의 일부를 또 다시 방문하게 된다고 하더라도 결과는 이미 탐색했을 때의 결과와 같게 된다.
• 따라서 각 경로를 매번 탐색하는 것이 아니라 chk배열의 값으로 탈출가능여부를 판단한다. 

1. chk가 0이 되는 경우는 미로탐색을 시작하기 이전인 초기화 상태일 때만 가능하다. → 초기화
2. chk가 -1이 되는 경우는 탐색을 시작한 후이고, 결과 값을 받기 이전인 상태이다. → 탐색중
3. chk가 1이 되는 경우는 미로를 탐색하다가 경계밖을 만나는 경우 1을 리턴하면서 저장된다. 리턴된 모든 경로에 대해서 해당 인덱스의 chk값이 1이 저장되게 된다. → 탈출 가능
4. chk가 2이 되는 경우는 미로를 탐색하다가 사이클을 이루게 될 때(자신의 경로를 다시 만남) 해당 경로로는 경계밖으로 절대 이동할 수 없으므로 탈출 불가능이고 2를 리턴한다. → 탈출 불가능

 

코드

메모리	시간
10920 KB	8 ms