[SWEA] [파이썬 S/W 문제해결 기본] 5일차 - 미로 (python)

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

🔥 작성 코드

T = int(input())

for test_case in range(1, T+1):
    N = int(input())
    arr = [input() for _ in range(N)]
    v = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            v[i][j] = int(arr[i][j])
            if arr[i][j] == '2':
                ni = i
                nj = j

    st = [(ni,nj)]
    di = [1, -1, 0, 0]
    dj = [0, 0, 1, -1]
    result = 0
    i = ni
    j = nj
    while st:
        if result == 1:
            break
        for d in range(4):
            if 0 <= i + di[d] < N and 0 <= j + dj[d] < N:
                ni = i + di[d]
                nj = j + dj[d]
                if v[ni][nj] != 1:
                    st.append((i, j))
                    i = ni
                    j = nj
                    if v[i][j] == 3:
                        result = 1
                        break
                    v[i][j] = 1

                    break
        else:
            i, j = st.pop()

    print(f'#{test_case} {result}')

⭕ 해설

1. arr로 입력받은 배열은 미로가 붙어서 입력되므로 문자열입니다.
2. 따라서 arr를 돌며 v에 int로 변형하여 저장합니다.
   • 바꾸지 않아도 되지만 제가 익숙한 형태의 리스트를 사용하기 위해 변형하였습니다.
   • 이 때 시작점인 2의 인덱스를 찾아줍니다.
3. 2에서 출발하여 사방으로 길을 찾아보고, 벽(해당 위치의 v값이 1)이 아니라면 있으면 들러주고 1로 바꿉니다.
   • st에 출발위치를 저장합니다. 
4. 만약 막다른 길이라면 st.pop()을 통해 이 전 위치를 불러와서 다시 탐색합니다.
5. st에 저장된 위치가 있을 때까지 반복합니다.
6. 길을 따라가는 와중에 3을 찾는다면 결과값에 1을 저장하고 종료합니다.

 

🚨 입력받을 때 input() 대신 list(map(int, input())) 했으면 됐는데 ...