미로(4875) Python(SW Expert Academy)

난이도 : D2

문제번호 : 4875

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

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

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

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

출력

#과 1번부터인 테스트케이스 번호, 빈칸에 이어 계산결과를 정수로 출력하거나 또는 ‘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

---

2. 문제풀이

파이썬 스택 2일차 연습문제 중 하나인 미로 문제이다. 0인 위치에 이동을 하고  리스트에 상, 하, 좌, 우 로 이동하는 좌표를 넣어준다. 함수를 이용한 DFS를 만들수도 있었는데 이번에는 스택을 이용한 DFS로 만들었다. 스택에 시작 위치를 넣어주고 스택이 빌때까지 반복문을 돌린다. 탑데이터를 임시변수에 저장한 후 데이터를 제거하고 상 하 좌 우 좌표데이터를 만든다음에 인덱스상을 넘어갔거나 0이 아닌경우를 걸러낸후 스택에 넣어준다. 계속 반복을하다가 목표 지점인 3에 도달할 경우 1을 출력하고 스택이 빌때까지 반복했지만 도달하지 못했다면 0을 출력한다.

 

---

3. 소스코드

#4875 D2 미로
 
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))