SWEA - 미로 찾기 (4875) [Python]

 문제

 

- NxN 크기의 미로에서 출발지에서 목적지에 도착하는 경로가 존재하는지 확인하여 도착할 수 있으면 1, 아니면 0을 출력한다. 출발지는 2이고 도착지는 3이다. 1은 벽이고 0이 진행할 수 있는 경로이다.

 

 

 

 문제 상황

 

- 방문 여부를 체크하며 방문하지 않은 곳을 방문하여 3이 아닐 시에 그 주변을 탐색한다.

 

 

 

 해결 전략

 

- search 함수를 만들어 방문 위치를 갱신하며 3을 찾고, 못찾았을 경우 그 주변의 0을 찾아 다시 그 위치에서 탐색을 시작한다.

 

 

 

 코드

 

# 0 통로, 1 벽, 2 출발점, 3 도착점
# 2에서 3으로 도착 가능하면 1, 아니면 0을 출력
 
# 주변에 3이 있는지 탐색하고, 없으면 0에서 다시 탐색하는 함수
 
def search(lst, x, y, check):
    global is_check
    # 하, 상, 좌, 우 검색
    dx, dy = [1,-1,0,0], [0,0,-1,1] 
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        # 주변 탐색이 구간을 벗어나지 않을 때 & 방문한 적이 없는 위치일 때
        if 0<=xx<len(lst) and 0<=yy<len(lst) and not check[xx][yy]:
            # 방문 여부를 갱신
            check[xx][yy] = True
            # 만약 도착한 곳이 목적지라면 가능 여부를 True로 바꿔준다.
            if lst[xx][yy] == 3 :
                is_check = True
            # 도착한 곳이 0이라면 갱신된 방문 여부를 가지고 다시 그 부분에서 체크를 진행한다.
            elif lst[xx][yy] == 0 :
                search(lst,xx,yy,check)
 
T = int(input())
for idx in range(T):
    N = int(input())
    # 미로 입력받기
    maze = [list(map(int, list(input()))) for _ in range(N)]
    # 방문 여부를 확인하는 리스트
    cache = [[False for _ in range(N)] for i in range(N)]
    # 3까지 도달 가능한지 여부 확인
    is_check = False
    for i in range(N):
        for j in range(N):
            # 출발지를 찾는다.
            if maze[i][j] == 2:
                search(maze, i, j, cache)
    if is_check:
        print(f"#{idx+1} 1")
    else:
        print(f"#{idx+1} 0")

 

 

 해설

 

- is_check를 전역변수로 넣어 검색한 결과를 담을 수 있게 하였다. 진행 한 곳이 1일 경우, 즉 벽일 경우는 어차피 움직일 수 없기 때문에 조건은 진행 가능한 0일 때와, 목적지인 3일 때만 존재한다.

 

 새로 학습한 것 & 실수 

 

- .

 

 

출처 - https://swexpertacademy.com/main/