[백준 17090번] 파이썬 - 미로 탈출하기

백준 17090 - 미로 탈출하기

시간 제한 1초, 메모리 제한 512MB

# 조건

• 크기가 N x M인 미로가 있고, 미로는 크기가 1 x 1 인 칸으로 나누어져 있다.
• 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다.
• 어떤 칸(r, c)에 적힌 문자가
  • U인 경우에는 (r-1, c)로 이동해야 한다.
  • R인 경우에는 (r, c+1)로 이동해야 한다.
  • D인 경우에는 (r+1, c)로 이동해야 한다.
  • L인 경우에는 (r, c-1)로 이동해야 한다.
• 미로에서 탈출 가능한 칸의 수를 계산해보자.
• 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

입력

• 첫째 줄에 미로의 크기 N, M(3 ≤ N, M ≤ 500)이 주어진다.
• 둘째 줄부터 N개의 줄에는 미로의 각 칸에 적힌 문자가 주어진다.

출력

• 첫째 줄에 탈출 가능한 칸의 수를 출력한다.

# 접근 방법

• bfs나 dfs를 이용하여 풀어줄 수 있다.
• dfs의 경우 아직 방문하지 않았다면 적혀있는 방향대로 탐색하며 탈출 가능한지를 return 해주면 된다.
  • 또는, 진행 중에 이미 다른 경로에서 방문한 적 있다면 이 경로가 탈출 가능한지 아닌지 나와있기 때문에 visited 값을 return 해주면 된다.
• bfs의 경우 주어진 배열을 먼저 탐색하며 탈출 가능한 곳을 q에 넣어준다.
  • 이후, 역방향으로 탐색해야 하는데 이를 위해서 DRUL 순으로 0 1 2 3으로 변경해주고, 4 방향을 탐색해주면 된다.
  • 즉, 현재 위치에서 1칸 위를 탐색한다면 1칸 위는 U를 나타내는 2가 적혀있어야 탈출 가능한 루트가 된다.
  • 마찬 가지로 진행 중 탈출 가능한 경로라면 continue 해주면 된다.

dfs 풀이

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
sys.setrecursionlimit(10**6)  

def dfs(ci, cj):  
    # 범위를 벗어났거나 이미 방문한 경로라면 return  
    if ci < 0 or ci >= N or cj < 0 or cj >= M:  
        return 1  
    if visited[ci][cj]:  
        return visited[ci][cj]  

    visited[ci][cj] = 2  
    visited[ci][cj] = dfs(ci+direct[maze[ci][cj]][0], cj+direct[maze[ci][cj]][1])  
    return visited[ci][cj]  

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

direct = {'U' : (-1, 0), 'D': (1, 0), 'R': (0, 1), 'L':(0, -1)}  
visited = [[0]*M for _ in range(N)]  

for i in range(N):  
    for j in range(M):  
        if not visited[i][j]:  
            dfs(i, j)  

result = 0  
for i in visited:  
    result += i.count(1)  
print(result)

bfs 풀이

### 위에는 dfs 풀이  
### 밑에는 bfs 풀이  

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

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

# 역방향 체크 위해서 DRUL 순  
# 역방향 계산 편하게 하기위해 DRUL -> 0123 변경해주고 탈출 가능 한 곳 can에 넣기  
di, dj = [1, 0, -1, 0], [0, 1, 0, -1]  
can = deque()  
visited = [[0]*M for _ in range(N)]  
result = 0  
for i in range(N):  
    for j in range(M):  
        if maze[i][j] == 'D':  
            maze[i][j] = 0  
        elif maze[i][j] == 'R':  
            maze[i][j] = 1  
        elif maze[i][j] == 'U':  
            maze[i][j] = 2  
        else:  
            maze[i][j] = 3  

        ni, nj = i+di[maze[i][j]], j+dj[maze[i][j]]  
        if not 0<=ni<N or not 0<=nj<M:  
            can.append((i, j))  
            visited[i][j] = 1  
            result += 1  

# 탈출 가능한 곳부터 역방향 탐색  
while can:  
    si, sj = can.popleft()  
    for d in range(4):  
        # 역방향이므로 범위를 벗어나면 안됨  
        # 역방향 체크 위해서는 1칸 위를 쳐다보면 U를 뜻하는 2가 있어야됨        
        ni, nj = si+di[d], sj+dj[d]  
        if 0<=ni<N and 0<=nj<M and visited[ni][nj] == 0:  
            if maze[ni][nj] == (d+2) % 4:  
                can.append((ni, nj))  
                visited[ni][nj] = 1  
                result += 1  

print(result)