[Python][백준 17090][DFS] 미로 탈출하기 - 컴도리돌이

반응형

17090번: 미로 탈출하기

---

풀이 과정

해당 문제는 DFS로 접근하였습니다.

똑같은 경로로 방문할 경우가 있을 때는 DFS로 접근하는 편이라,,😊

 

1. n, m 그리고 미로 그래프를 입력받는다.

 

2. 방문 표시를 하기 위해 "visited" 이름으로 n x m 크기의 배열을 생성한다.

 

3. n x m 만큼 반복문을 돌려준다.

해당 (i, j) 좌표로 시작하는 경로로 탐색한 경우가 없을 경우 dfs 탐색 시작.

 

4. DFS 탐색

4-1) 현재 좌표 값(x, y)이 미로를 탈출할 경우 1을 반환.

4-2) 현재 좌표 값으로 방문 값이 있을 경우 해당 값을 반환

4-3) 현재 좌표 값을 -1로 설정

4-4) 다음 경로로 dfs 탐색 

(x, y) -> 현재 위치에 쓰여있는 방향으로 다음 좌표 탐색

해당 값을 현재 좌표의 visited에 저장

4-5) 현재 방문 값 반환

---

풀이 코드

import sys; input = sys.stdin.readline ; sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
maze = [list(input().strip()) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
dir = {"U":0,"R":1,"D":2,"L":3}
dx,dy,answer = [-1,0,1,0],[0,1,0,-1],0 
def search(x,y) :
  if x < 0 or x >= n or y < 0 or y >= m : return 1
  if visited[x][y] : return visited[x][y]
  visited[x][y] = -1
  visited[x][y] = search(x + dx[dir[maze[x][y]]],y + dy[dir[maze[x][y]]])
  return visited[x][y]

for i in range(n) :
  for j in range(m) :
    if not visited[i][j] and search(i,j) == 1 : answer+=1 
    elif visited[i][j] == 1 : answer += 1
print(answer)