17090번: 미로 탈출하기
크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문
www.acmicpc.net
문제
크기가 N×M인 미로가 있고, 미로는 크기가 1×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개의 줄에는 미로의 각 칸에 적힌 문자가 주어진다.
출력
첫째 줄에 탈출 가능한 칸의 수를 출력한다.
코드
import sys
sys.setrecursionlimit(10000000)
def dfs(x, y):
visited[x][y] = 0
if maze[x][y] == 'U':
nx, ny = x-1, y
elif maze[x][y] == 'R':
nx, ny = x, y+1
elif maze[x][y] == 'D':
nx, ny = x+1, y
elif maze[x][y] == 'L':
nx, ny = x, y-1
if nx < 0 or nx >= n or ny < 0 or ny >= m: # 탈출
visited[x][y] = 1
elif visited[nx][ny] == -1: # 아직 방문 안 한 칸
visited[x][y] = dfs(nx, ny)
else: # 이미 방문한 칸
visited[x][y] = visited[nx][ny]
return visited[x][y]
n, m = map(int, input().split())
maze = []
visited = [[-1] * m for _ in range(n)]
for _ in range(n):
maze.append(list(input()))
for i in range(n):
for j in range(m):
if visited[i][j] == -1:
dfs(i, j)
ans = 0
for i in range(n):
ans += sum(visited[i])
print(ans)
DFS와 DP를 이용하여 풀이하였다.
visited 2차원 배열에 초기값으로 -1을 채워준다. 그리고 dfs로 탐색하는데 방문한 칸([x, y])은 0으로 표시하고 그 칸에서 다음에 이동할 칸([nx, ny])을 살펴본다.
- 다음 칸이 경계 밖 : 현재 칸이 탈출 가능한 칸이라는 말이므로 visited[x][y] = 1
- 다음 칸의 visited 값이 -1 : 아직 방문 안 한 칸이므로 dfs 탐색 진행
- 다음 칸의 visited 값이 0 또는 1 : 이미 탐색한 칸이므로 dfs를 수행할 필요는 없다. visited[x][y] = visited[nx][ny]
모든 칸에 대해 dfs를 수행하고 나면 visited 배열의 모든 값은 0 또는 1일 것이다. 탈출 가능한 경로가 있는 칸들의 visited 값은 1일 것이므로 visited 배열의 값들의 합을 구해주면 답이다.
RecursionError가 발생해서 setrecursionlimit으로 재귀 깊이를 조절해주었더니 해결되었다.
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 17471번 게리맨더링 (0) | 2023.08.26 |
---|---|
[Python/파이썬] 백준 21937번 작업 (0) | 2023.08.19 |
[Python/파이썬] 백준 18404번 현명한 나이트 (0) | 2023.08.17 |
[Python/파이썬] 백준 1520번 내리막 길 (0) | 2023.07.31 |
[Python/파이썬] 백준 3187번 양치기 꿍 (0) | 2023.07.21 |