[SWEA] 4875 미로(백트래킹) - python

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIc7KqfQDFAWg 

SW Expert Academy

1. 출발지점, 도착지점 찾기

2. stack에 현재 좌표 넣기

3. 스택에서 현재 좌표 pop

4. 주변에 갈 수 있는 곳 찾기

5. 갈 수 있으면 stack에 추가 후, 방문 표시

6. 갈 수 없으면 pass

-> 다시 처음으로 돌아가 마지막으로 방문한 좌표 스택에서 꺼내고, 

갈 수 있는곳 찾기 반복

 

7. 반복문이 끝난 후 목표 지점에 방문했는지 안했는지 검사

 

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input())) for _ in range(N)]
    stack = []
    visited = [[False] * N for _ in range(N)]
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    # 출발 지점, 도착 지점 찾기
    for y in range(N):
        for x in range(N):
            if arr[y][x] == 2:
                start_y = y
                start_x = x
            if arr[y][x] == 3:
                goal_y = y
                goal_x = x
    # 출발 좌표 stack에 넣기
    stack.append([start_y, start_x])

    while stack:
        # stack에서 마지막 좌표 꺼내기
        y, x = stack.pop()
        for k in range(4):
            ny, nx = y + dy[k], x + dx[k]
            # 도착점에 도착하면 방문 표시 후 break
            if ny == goal_y and nx == goal_x:
                visited[ny][nx] = True
                break
            # ny, nx가 N보다 작고
            if 0 <= ny < N and 0 <= nx < N:
                # 다음 지점이 0이고, 방문하지 않았으면
                if arr[ny][nx] == 0 and visited[ny][nx] == False:
                    # 스택에 지점 추가 + 방문표시
                    stack.append([ny,nx])
                    visited[ny][nx] = True
                # 갈 곳이 없으면 pass
                else:
                    continue
                    
    # 다 돈후 목표 지점을 방문했으면 1
    if visited[goal_y][goal_x] == True:
        print(f'#{test_case} 1')
    else:
        print(f'#{test_case} 0')