728x90
반응형
17090번: 미로 탈출하기
크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문
www.acmicpc.net
풀이 과정
해당 문제는 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)728x90
