1227. [S/W 문제해결 기본] 7일차 - 미로2(DFS, BFS)

문제: 무단 배포 금지로 인해 사이트 주소로 남깁니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14wL9KAGkCFAYD

SW Expert Academy

 

정답 코드:

T = 10  #테스트 케이스
from collections import deque
for _ in range(T):
    answer = 0
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    r = 0
    c = 0
    test_case = int(input())

    maze = [list(input()) for _ in range(100)]
    cols = len(maze[0])
    rows = len(maze)


    flag = False
    for row in range(rows):
        for col in range(cols):
            #row와 col이 시작인덱스를 가지도록
            if maze[row][col] != '2':
                continue
            r = row
            c = col
            flag = True
            break
        if flag:
            break
    # #DFS
    # stack = [(r, c)]
    # while stack:
    #     row, col = stack.pop()
    #     # 지나온 길은 벽으로 만들어 버리기
    #     maze[row][col] = '1'
    #     # 상하좌우 살피기
    #     for i in range(4):
    #         nx = row + dx[i]
    #         ny = col + dy[i]
    #         #도착지를 발견하면
    #         if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == '3':
    #             answer = 1
    #
    #         if nx < 0 or nx >= rows or ny < 0 or ny >= cols or maze[nx][ny] != '0':
    #             continue
    #         stack.append((nx, ny))
    # print(f"#{test_case} {answer}")

    # BFS
    queue = deque([(r,c)])
    while queue:
        row, col = queue.popleft()
        #아래 동일
        #-------------------------
        # 지나온 길은 벽으로 만들어 버리기
        maze[row][col] = '1'
        # 상하좌우 살피기
        for i in range(4):
            nx = row + dx[i]
            ny = col + dy[i]
            # 도착지를 발견하면
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == '3':
                answer = 1

            if nx < 0 or nx >= rows or ny < 0 or ny >= cols or maze[nx][ny] != '0':
                continue
            queue.append((nx, ny))#여기 stack만 queue로 바꿈
    print(f"#{test_case} {answer}")