[파이썬] 4875. 미로

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

SW Expert Academy

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


NxN 크기의 미로에서 출발지에서 목적지에 도착하는 경로가 존재하는지 확인하는 프로그램을 작성하시오. 도착할 수 있으면 1, 아니면 0을 출력한다.

주어진 미로 밖으로는 나갈 수 없다.

다음은 5x5 미로의 예이다.
 

13101

10101

10101

10101

10021

 

마지막 줄의 2에서 출발해서 0인 통로를 따라 이동하면 맨 윗줄의 3에 도착할 수 있는지 확인하면 된다.

 
 

[입력]
 

첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50
 

다음 줄부터 테스트 케이스의 별로 미로의 크기 N과 N개의 줄에 걸쳐 미로의 통로와 벽에 대한 정보가 주어진다. 0은 통로, 1은 벽, 2는 출발, 3은 도착이다. 5<=N<=100

 

[출력]
 

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 계산결과를 정수로 출력하거나 또는 ‘error’를 출력한다.

입력	출력
3 5 13101 10101 10101 10101 10021 5 10031 10111 10101 10101 12001 5 00013 01110 21000 01111 00000	#1 1 #2 1 #3 0

 

🎀 다른사람 풀이

 

def IsSafe(y, x):		# 인덱스 범위 체크, 통로 0 또는 목적지면 계속 탐색
    return 0<=y<N and 0<=x<N and (Maze[y][x] == 0 or Maze[y][x] ==3)

def DFS(start_y, start_x):
    global result

    if Maze[start_y][start_x] == 3:     # 도착하면
        result=1
        return

    visited.append((start_y, start_x))
    for dir in range(4):		# 상하좌우 탐색
        New_Y=start_y+dy[dir]
        New_X=start_x+dx[dir]
        if IsSafe(New_Y, New_X) and (New_Y, New_X) not in visited:	# 인덱스 범위, 값, 미방문이면 
            DFS(New_Y, New_X)

TC=int(input())
for tc in range(1, TC+1):
    N=int(input())
    Maze=[list(map(int, input())) for _ in range(N)]

    for y in range(N):
        for x in range(N):
            if Maze[y][x] == 2 :
                start_y, start_x = y, x			# 출발점의 index를 저장

    # 상하좌우
    dy=[-1, 1, 0, 0]
    dx=[0, 0, -1, 1]

    visited=[]
    result=0
    DFS(start_y, start_x)
    print('#%d %d' %(tc, result))

 

Maze에서 출발점의 index를 구한다.

인덱스를 visited에 추가해서 방문 처리한다.

dy, dx에 있는 값과 더해서 상하좌우를 탐색한다. 인덱스의 범위가 0보다 크거나 같고 N보다 작아야한다.

값이 1이면 탐색할 필요가 없어서 0또는 3일때만 return

3을 만날 때까지 계속해서 재귀호출한다.

 

move_list=[(1, 0), (-1, 0), (0, 1), (0, -1)]

# 바운더리 체크
def iswall(y, x):
    if y < 0 or x < 0 or y >= N or x >= N :
        return True
    return False

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

    # 2가 있는 위치 찾기
    for i in range(N) :
        if 2 in map_list[i] :
            x=map_list[i].index(2)
            y=i
            break

    # 스택에 시작위치 넣어주기
    stack = [(y, x)]

    # 스택이 빌 때까지 반복
    while stack :
        temp_list=[]
        # 스택에 있는 값을 꺼내서
        y, x=stack.pop()
        # 현재 위치는 갔다고 변경
        map_list[y][x]=1
        # 이동할 4방향을 검사
        for _y, _x in move_list :
            dy=y+_y
            dx=x+_x
            # 가는 길이 바운더리 벗어나면 다음길로
            if iswall(dy, dx) :
                continue
            # 가는 곳이 3이면 도착지점
            if map_list[dy][dx] == 3 :
                # 결과 변경 후 반복문 종료
                result=1
                break
            # 0이라면 갈 수 있는 장소를 스택에 추가
            elif not map_list[dy][dx] :
                stack.append((dy, dx))
        else :
            # 브레이크 없이 끝났다면 다음 것으로 진행
            continue
        # 브레이크 문으로 여기까지 왔다면 반복 멈추기
        break
    # 결과 출력
    print('#{} {}'.format(t, result))

 

위와 같은 알고리즘인데 스택으로 구현함.

not map_list[dy][dx]는 0을 의미.