[SWEA] 1226.미로 1 (dfs)

풀어도 풀어도 어려운 dfs, bfs.. 이번에 볼 문제는 SWEA 문제해결 기본 미로 I 이다. (예전에 풀었던 기억을 더듬어서 응용 문제로 바로 들어갔다가 다시 기초로 돌아왔다 ㅎㅎㅎ)

문제

• SWEA 1126 미로1 D4
• Python
• 문제링크

SW Expert Academy

접근

기본적인 DFS 접근으로 풀면 되는 문제다. 시작점(2)을 찾은 후, 상하좌우를 탐색해 나가면서 도착점(3)을 찾으면 1을 리턴, 못 찾을 시는 0을 리턴한다.

코드

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
for _ in range(10):
    answer = 0
    n = int(input())
    maps = [list(input()) for _ in range(16)]

    
    x, y = 0, 0
    for i in range(16):
        for j in range(16):
            if maps[i][j] == '2':                   # 출발점 찾은 후 인덱스 저장
                x, y = i, j

                                                    # DFS 탐색 시작
    stack = [(x, y)]                                
    while stack:                                    # 스택이 존재 할 때
        cx, cy = stack.pop()                        # 스택에 있는 첫 번째 인덱스를 가져온다            
        
        for k in range(4):                          # 상하좌우 탐색 시작
            nx = cx + dx[k]                         # 탐색 후 재 설정된 row index
            ny = cy + dy[k]                         # 탐색 후 재 설정된 col index
            if 0 <= nx < 16 and 0 <= ny < 16:       # 전체 미로의 크기 안에서 탐색
                if maps[nx][ny] == '0':             # 재설정된 인덱스의 미로 값이 0, 즉 길이면
                    stack.append((nx, ny))          # 탐색을 위해 stack에 append
                    maps[nx][ny] = '4'              # 이미 탐색한 길이니 0이 아닌 다른 숫자로 재설정해준다
                elif maps[nx][ny] == '3':           # 재설정된 인덱스의 미로 값이 3, 즉 도착점이면ㄴ
                    answer = 1                      # answer = 1
                    stack.clear()               
                    break                           # 탐색 종료

    print('#{} {}'.format(n, answer))   

 

DFS의 핵심은 

1. 갈랫길에서의 다른 path 꼭 저장해주기

2. visited track 해주기