[맛있는물회] <SWEA알고리즘> 4875번 "미로"

문제 조건

---

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

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

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

13101

10101

10101

10101

10021

 

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

 

Input

---

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

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

 

Output

---

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

 

 

생각한 아이디어

---

재귀 DFS만 구현한다면 아주 쉽게 풀릴문제이다. 

그런데 나는 맨첨에 DFS로 접근한 것이 아니라 stack을 구현해서 하겠다고 생각했다.

그랬더니 어마어마한 수의 케이스가 발생했다. 그렇게 엄청난 시간을 투자했지만 실패,,,,

 

그래서 다시 DFS로 갈아타고 구현했더니 코드가 굉장히 짧게 구현되었다.,...

N * N 미로 같은 문제에서는 dx,dy를 만들어서 상하좌우 움직이는 DFS가 제일인 듯 하다.

 

 

소스코드

#4875 "미로"
# find 함수 제대로 익혀놓기! 찾고자하는 문자의 index를 반환할 수 있다.
#너무 어려웠다.
#맨첨에는 재귀 안쓰고 그냥 stack을 사용해서 풀려고 했는데 
#아!! 스택쓰고 visited 잘 썼다면 풀 수 있었을 수도?? 근데 너무 식이 복잡해져서 힘들었다.
#그래서 재귀함수 사용한 dfs를 이용했더니 너무 쉽게 풀렸따...
#저번에 풀어본 재귀 안쓴 dfs와 재귀 사용한 dfs를 한번 정리하자 진짜....
# dfs 문제중에 쉬운 문제일텐데 너무 힘들게 풀었다.. 반성하자.

def dfs(j,i):
    global ans
    if maze[j][i] == '3':
        ans = 1
        return
    visited.append((j,i))
    for dir in range(0,4):
        newj = j + dy[dir]
        newi = i + dx[dir]
        if 0 <= newj < N and 0 <= newi < N and maze[j][i] !='1' and (newj,newi) not in visited:
            dfs(newj,newi)
    #(maze[j][i] == '1' or maze[j][i] == '3') 

T = int(input())
for TC in range(1, T + 1):
    N = int(input())
    maze = list()
    for i in range(0,N): #지도 입력
        arr = str(input())
        maze.append(arr)
        if '2' in arr:
            j_start = i
        if '3' in arr:
            j_end = i
    i_start = maze[j_start].find('2')
    i_end = maze[j_end].find('3')

    visited = list()

    i_cur = i_start
    j_cur = j_start
    
    dy = [-1,1,0,0] #상하좌우
    dx = [0,0,-1,1]
    ans = 0
    dfs(j_start,i_start)

    if ans == 1:
        print("#%d %d" %(TC, 1))
    else:
        print("#%d %d" %(TC, 0))

    '''
    while 1:
        if i_cur == i_end and j_cur == j_end: 
            ans = 1
            break
        if flag == 1:#좌
            if i_cur - 1 <0 or maze[j_cur][i_cur-1] == '1' or (i_cur, j_cur) in visited:
                #좌표에서 벗어나거나, 벽으로 막혀있으면
                flag += 1
            else:
                visited.append((i_cur, j_cur))
                i_cur -= 1
                stk.append((i_cur, j_cur, flag))
        elif flag == 2:#상
            if j_cur - 1 <0 or maze[j_cur -1][i_cur] == '1' or (i_cur, j_cur) in visited:
                #좌표에서 벗어나거나, 벽으로 막혀있으면
                flag += 1
            else:
                visited.append((i_cur, j_cur))
                j_cur -= 1
                stk.append((i_cur, j_cur, flag))
                flag = 1# 다시 왼쪽부터 돌게하기
        elif flag == 3:#우
            if i_cur + 1 <0 or maze[j_cur][i_cur+1] == '1' or (i_cur, j_cur) in visited:
                #좌표에서 벗어나거나, 벽으로 막혀있으면
                flag += 1
            else:
                visited.append((i_cur, j_cur))
                i_cur += 1
                stk.append((i_cur, j_cur, flag))
                flag = 1
        elif flag == 4:#하
            if j_cur + 1 <0 or maze[j_cur + 1][i_cur] == '1' or (i_cur, j_cur) in visited:
                #좌표에서 벗어나거나, 벽으로 막혀있으면
                flag += 1
            else:
                visited.append((i_cur, j_cur))
                j_cur += 1
                stk.append((i_cur, j_cur, flag))
                flag = 1
        elif flag == 5: #한바퀴 다돌면 stack 에서 pop하고 뒤로가야함
            back = stk.pop()
            i_cur = back[0]
            j_cur = back[1]
            flag = back[2] + 1
            '''
            

 

*파이썬 문법 정리