[Python/DailyAlgo] 62. 미로 찾기 1

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

DFS/BFS

https://dailyalgo.kr/ko/problems/62

---

풀이

DFS 풀이

# DFS
# 코테 수준에서는, 재귀 호출 깊이를 1000을 초과하지 않게 냄.
# 왜냐면 자바나 C++은 걍 초과해버려서. 
# 근데 이런 백준 이런건 이렇게 재취 깊이가 1000이 넘어가는 문제를 내기도 함.
# 따라서, 그냥 풀면 `Recursionerror`가 나옴.

import sys
sys.setrecursionlimit(10**6)

def solution(maze):
    def dfs(x, y):

        # 3. 이동하기
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            # 4. 범위 확인
            if 0 <= nx < n and 0 <= ny < n and maze[nx][ny] == 0 and not visited[nx][ny]:
                if nx == n - 1 and ny == n - 1:
                    nonlocal answer
                    answer = True
                    return
                visited[nx][ny] = True
                dfs(nx, ny)

    n = len(maze)
    # 싸이클 돌지 않도록
    visited = [[False] * n for _ in range(n)]

    # 1. 기준 잡기 
    # => 밑에 dfs 호출에서 할 거임.

    # 2. 상하좌우 델타값 정의
    answer = False
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    # dfs에서 출발점은 먼저 방문처리
    visited[0][0] = True
    dfs(0, 0)

    return answer
    # sol1) return visited[-1][-1]
    # sol2) if x, y == n-1, n-1 -> return True

# 입력 : 미로판을 의미하는 행렬 maze
# 출력 : 시작 지점 (1, 1)부터 (n, n)으로 나갈 수 있는지 여부

BFS 풀이

from collections import deque
def solution(maze):

    def bfs():
        # 좌표는 하나니까, 저렇게 괄호로 넣어줌.
        # 이터러블 안에 꺼를 요소로 가지니까 튜플이 들어감.
        queue = deque([(0, 0)])
        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if 0 <= nx < n and 0 <= ny < n and maze[nx][ny] == 0 and not visited[nx][ny]:
                    if nx == n - 1 and ny == n - 1:
                        nonlocal answer
                        answer = True
                        return

                    # 이렇게 bfs는 '간다'는 행위가, 
                    # 다음에 방문 가능한 정점을 queue에 넣어주는 것임.
                    visited[nx][ny] = True
                    queue.append((nx, ny))


    n = len(maze)
    visited = [[False] * n for _ in range(n)]
    answer = False

    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

    visited[0][0] = True
    bfs()

    return answer

    # 이 문제는 bfs로 풀어야 최단거리까지 구할 수 있음.
    # 강사님 그림 그려주신 거 상기. 물결무늬 퍼져나가는 그림.

---

250218 재풀이

DFS 풀이

import sys
sys.setrecursionlimit(10**6)
def solution(maze):

    n = len(maze)
    # 1. 기준점 잡기
    x, y = 0, 0

    # 2. 상하좌우 델타값 정의
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    visited = [[False] * n for _ in range(n)]

    def dfs(x, y):
        # 2. 재귀하며 현재 정점에서 action 실행(여기선 x)
        
        # 3. 인접한 모든 정점들에 대해,
        # 3. 이동하기
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 4. 방문x 인접 정점으로 이동(함수 호출)
            # 4. 범위 확인
            if 0 <= nx < n and 0 <= ny < n and maze[nx][ny] == 0 and not visited[nx][ny]:
                if nx == n - 1 and ny == n - 1:
                    nonlocal answer
                    answer = True
                visited[nx][ny] = True
                dfs(nx, ny)


    answer = False
    # 1. 시작 정점 방문 처리
    visited[x][y] = True
    dfs(x, y)

    return answer

BFS 풀이

from collections import deque
def solution(maze):

    n = len(maze)
    # 1. 기준점 잡기
    x, y = 0, 0

    # 2. 상하좌우 델타값 정의
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    visited = [[False] * n for _ in range(n)]

    def bfs(x, y):
        queue = deque([(x, y)])
        # 2. queue가 빌 때까지,
        while queue:
        # 3. pop하며 현재 정점에서 action 실행(여기선 x)
            x, y = queue.popleft()
            # 4. 인접한 모든 정점들에 대해,
            # 3. 이동하기
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                # 5. 방문x 인접 정점으로 이동(함수 호출)
                # 4. 범위 확인
                if 0 <= nx < n and 0 <= ny < n and maze[nx][ny] == 0 and not visited[nx][ny]:
                    if nx == n - 1 and ny == n - 1:
                        nonlocal answer
                        answer = True
                        return
                    visited[nx][ny] = True
                    queue.append((nx, ny))


    answer = False
    # 1. 시작 정점 방문 처리
    visited[x][y] = True
    bfs(x, y)

    return answer