4875. [파이썬 S/W 문제해결 기본] 5일차 - 미로 코드분석

 

🚛 파이썬 SW문제해결 기본 - Stack2

델타값과 스택을 활용해서 상하좌우 4방향을 체크하는 문제입니다.
델타값을 이용해서 4방향을 체크할때에 배열의 범위를 벗어나지 않도록 체크하는 것이 중요합니다.

 

 

💡 아이디어

 DFS 알고리즘을 기반으로 미로의 시작점에서 부터 4방향을 체크해가며  
 목적지를 찾아나가는 방식으로 코드를 구성했습니다. Stack에는 이동가능한 곳들을  
 담아주고 방문한 곳은 기본 배열에서 0으로 초기화 되어있던 것을 1로 바꾸어줍니다.  
 계속해서 이동하며 목적지인 3에 도착하면 break하여 반복문을 빠져나옵니다.

 

🎲 파이썬 코드

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

"""
- 문제
    미로 : 2(출발), 3(도착), 0(통로), 1(벽)
    도착할 수 있으면 1 출력, 아니면 0 출력
    미로는 NxN (5<=N<=100)

- 아이디어
    DFS
"""
T = int(input())

# 상하좌우 델타값.
moves = [(1, 0), (-1, 0), (0, -1), (0, 1)]

# 바운더리를 체크해주는 함수..
def isWall(x,y):
    if x < 0 or y < 0 or y >= N or x >= N:
        return True
    return False

for tc in range(1, T+1):
    N = int(input())
    BRD = [list(map(int, input())) for _ in range(N)]
    x, y = 0, 0

    # 시작지점 구하기.
    for i in range(N):
        if 2 in BRD[i]:
            x = BRD[i].index(2) # 열
            y = i # 행
            break

    # 이동가능한 곳을 저장하는 Stack에 첫번째 위치 인덱스 넣어주기.
    Stack = [(y, x)]
    result = 0
    while Stack:
        # 스택에서 시작점 인덱스 가져오기.
        y, x = Stack.pop()
        # 현재위치는 방문했으므로 1로 변경
        BRD[y][x] = 1

        for _y, _x in moves:
            # 상하좌우 방향으로 인덱스 이동하기..
            dy = y + _y
            dx = x + _x

            # 바운더리 체크. 주변이 가로막혔다면 다음 인덱스로 이동..
            if isWall(dy, dx):
                continue

            # 가는 곳이 3이라면 result 1로 바꾸고 break
            if BRD[dy][dx] == 3:
                result += 1
                break

            # 0이라면 이동할 수 있는 곳, Stack에 저장.
            elif not BRD[dy][dx]:
                Stack.append((dy, dx))

        # 상하좌우 다 검사하고 break가 없다면 다음으로 이동.
        else:
            continue
        # break로 이곳에 도달하였다면 while문 종료.
        break

    print('#{} {}'.format(tc, result))

* 제 코드가 정답은 아닙니다. 부족한 부분과 더 좋은 아이디어가 있으시면 댓글로 남겨주세요! :)