[Python Algorithm] 미로1 SWEA #1226

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD 

SW Expert Academy

 

내 문제 풀이

for _ in range(10):
    t = int(input())
    maze = [[] for _ in range(16)]
    start = (0, 0)
    check = False

    for i in range(16):
        now = list(map(int, list(input())))
        if 2 in now:
            tmp = now.index(2)
            start = (i, tmp)
        maze[i] = now

    def dfs(x, y):
        global check
        if x < 0 or y < 0 or x >= 16 or y >= 16 or maze[x][y] == 1 or check: return

        if maze[x][y] == 3:
            check = True
            return
        if maze[x][y] == 0 or 2:
            maze[x][y] = 1

        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)

    dfs(start[0], start[1])
    print("#" + str(t) + " " + ("1" if check else "0"))

👉 DFS 문제 ! (BFS 풀이도 아래에 있어용)

• 미로 정보를 입력받으면서 시작지점의 좌표값도 함께 찾아준다.
  그리고 이 시작지점 좌표를 인자로 보내서 dfs를 실행시킨다.
• 좌표가 탐색할 수 없거나 탐색할 필요 없는 위치일 경우를 예외처리해준다.
  1) 미로 범위를 벗어난 경우
  2) 1일 경우 (벽이거나 이미 지나갔던 자리인 경우)
  3) check가 True인 경우 (이미 도착지점에 도달할 수 있다는 것 확인된 경우)
• 그리고 해당하는 위치가 3인 경우는 도착 지점에 도달한 것이므로
  check를 True로 바꿔서 도착에 성공했다는 것을 표시해주고, 리턴한다.
• 해당하는 위치가 0이거나(벽도 아니며 지나가지도 않았던 자리), 2라면(시작 지점)
  그 자리를 1로 채워주어서 다시 똑같은 자리를 탐색하는 일이 없도록 해준다.
• 그리고 현재 좌표의 상하좌우 위치에 대한 탐색을 할 수 있도록 dfs함수를 재귀호출해준다.
• dfs함수 종료 후에는 check가 True인지 False인지 여부에 따라 값을 출력한다.

 

BFS 문제 풀이

import copy
from collections import deque

for _ in range(10):
    t = int(input())
    maze = [[] for _ in range(16)]
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    start = (0, 0)
 
    for i in range(16):
        now = list(map(int, list(input())))
        if 2 in now:
            tmp = now.index(2)
            start = (i, tmp)
            now[tmp] = 1 # 시작 지점은 다시 올 필요가 없으므로 처음부터 1로 바꿔주기
        maze[i] = now
 
    def bfs(deq):
        while deq:
            (x, y) = deq.popleft()
 
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
 
                if nx < 0 or ny < 0 or nx >= 16 or ny >= 16 or maze[nx][ny] == 1:
                    continue
 
                if maze[nx][ny] == 3:
                    return True
                else:
                    maze[nx][ny] = 1
                    deq.append((nx, ny))
        return False
 
    deq = deque()
    deq.append(start)
    print("#" + str(t) + " " + str(1 if bfs(deq) else 0))

이 문제의 경우 DFS가 훨씬 효율적이지만, BFS도 가능할 것 같아 풀이해보았다.

(알고리즘은 다르지만 전체적인 풀이 흐름은 비슷하기 때문에 따로 설명하진 않겠습니당)

 

💡 피드백

• 어렵지 않은 문제였지만 요즘 왜그런지 모르겠는데 자꾸 이상한 곳에서 실수해서,,
  오랜시간 헤매고 있는 상황이 넘 많아졌다.;; 정신차리고 풀자 ~~~