[Python] BOJ 2178 미로탐색

요구사항

• 시간 제한 1초
  • 2이상 n, m 이 100 이하 정수로 이루어져 있으니 O(n**2) 도 무리 없어 보인다.
• 메모리 제한 192MB 
  • 아무리 해도 괜찮아 보인다.
• (1, 1) 에서 출발하여 (N, M) 즉, 오른쪽 하단까지 가는 최소거리를 구하라. 

설게 1

• n, m 을 입력받는다.
• 2차원 배열을 초기화 한다.
• 방문여부를 불리언으로 초기화한다.
• 최소값을 구할 miniu을 초기화한다.
• bfs를 구현한다.
• 모든 경우의 수를 다 넣어보고 가장 적은 값을 출력한다.

구현 1

import sys
from collections import deque

n, m = map(int, input().split())

# 2차원 배열 초기화
mirro = [list(map(int, input().split())) for _ in range(n)]
# 방문 여부
visited = [[False] * m for _ in range(n)]

mininum = sys.maxsize

def bfs(x, y):
    queue = deque([(x, y)])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]    
    visited[x][y] = True
    min_count = 1

    while queue:
        cx, cy = queue.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and mirro[nx][ny] == 0:
                visited[nx][ny] = True
                queue.append((nx, ny))
                min_count += 1
    return min_count

for i in range(n):
    for j in range(m):
        if mirro[i][j] == 1 and not visited[i][j]:
            mininum = min(mininum, bfs(i, j))

print(mininum)

실수 :

• list index out of range: 
  • 계속 범위를 바꿔봐도 나오질 않는다. 

설계 2

• 같은 로직으로 가지만 방문여부를 1이냐 아니냐로 판단이 가능하다. 
• maze == 1일 경우는 방문하지 않은 경우이고
  • 위 경우일 때, 방문한 위치에서 인접한 maze == 1이니 방문한 곳의 + 1 을 해준다.
• maze == 1이 아닐 경우에는 방문한 경우이다.

구현 2

from collections import deque

# 입력 받기
n, m = map(int, input().split())
maze = [list(map(int, input().strip())) for _ in range(n)]

# 방향 벡터 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 함수 정의
def bfs(x, y):
    queue = deque([(x, y)])
    while queue:
        x, y = queue.popleft()
        
        # 네 방향으로 이동
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            # 미로 범위 안에 있고, 이동 가능한 칸일 경우
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1
                queue.append((nx, ny))
    
    # (n-1, m-1) 위치의 값 반환 (최소 이동 횟수)
    return maze[n-1][m-1]

# 결과 출력
print(bfs(0, 0))

 

•