Python3
문제
https://www.acmicpc.net/problem/2178
키워드
- 그래프
- 최단 거리
문제 풀이
문제 요구사항
- (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램
- 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다
- 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
=> 위아래, 좌우 (dy = [-1, 0, 1, 0] , dx = [0, -1, 0, 1])
변수 및 함수 설명
- n : n개의 줄
- m : m개의 정수 (2 ≤ N, M ≤ 100)
- adjMatrix : 행렬을 담는 2차원 배열 (붙어서 입력으로 주어진다)
- visited : 방문했는지 확인하는 2차원 배열
- dy : 위 아래(상하) 탐색
- dx : 좌우 탐색
- currentLocation : 큐에서 첫 번째 튜플에 꺼내 넣는다
- curY : 현재 y
- curX : 현재 x
- ny : 다음 번에 탐색할 y
- nx : 다음 번에 탐색할 x
- bfs() : bfs(너비우선탐색) 구현 함수
풀이
최단 거리 문제로 bfs 를 사용해서 푼다
인접 행렬 adjMatrix
(입력 및 선언)
- n, m을 입력받는다
- nxm개의 visited 배열을 만든다
- adjMatrix를 선언한다
- bfs를 사용하기 위해 bfsQueue를 선언한다 (deque)
- dy, dx를 선언한다
- 미로를 입력받으면 리스트로 만들어서 adjMatrix에 넣는다(2차원 배열로 만들기)
(dfs 함수)
- 큐에 원소가 있을 때까지 반복한다.
- currentLocation에 큐 첫 번째 원소 값을 넣는다. (튜플)
- 튜플의 첫 번째 원소는 현재 y좌표, 두 번째 원소는 현재 x좌표가 된다.
- 총 4번 반복한다 (상하좌우)
- 다음 이동할 y, x좌표는 각각 curY에 dy[i]를 더한 값과 curX에 dx[i]를 더한 값이다.
- 하지만 다음 이동할 좌표가 아래 조건 중 하나라도 만족하면 이동하지 않는다.
1) 현재 좌표가 (0, 0), (n-1, m-1) 일 때 다음 이동하는 곳이 밖이면 안 된다.
if ny < 0 or nx < 0 or ny >= n or nx >= m2) 다음 이동할 칸이 0이라면 갈 수 없다.
if adjMatrix[ny][nx] == 03) 이미 방문한 곳은 또 가지 않는다.
if visited[ny][nx] != 0- 해당하지 않으면 visited[ny][nx]에 (현재 누적 값 + 1)을 해준다.
- 큐에 (ny, nx) 값을 넣는다.
(함수 호출)
- 처음 출발하는 곳을 방문 처리하고 그 값(0, 0)을 큐에 넣는다.
- bfs 함수를 호출한다
- visited[n-1][m-1] 값을 출력한다.
최종 코드
from collections import deque
n, m = map(int, input().split())
adjMatrix = []
visited = [[0 for _ in range(m)] for _ in range(n)]
bfsQueue = deque([])
dy = [-1, 0, 1, 0] # 시계 방향
dx = [0, 1, 0, -1]
for i in range(n):
adjMatrix.append(list(map(int, input())))
# bfs - Queue
def bfs() :
while bfsQueue :
currentLocation = bfsQueue.popleft()
curY = currentLocation[0]
curX = currentLocation[1]
for i in range(4) :
ny = curY + dy[i]
nx = curX + dx[i]
# 가장자리일 때 미로를 넘어가면 패스
if ny < 0 or nx < 0 or ny >= n or nx >= m:
continue
# 0 은 벽이라서 이동할 수 없음
if adjMatrix[ny][nx] == 0 :
continue
# 이미 방문한 곳이면 패스
if visited[ny][nx] != 0 :
continue
visited[ny][nx] = visited[curY][curX] + 1
bfsQueue.append((ny, nx))
# bfs - 방문 처리, 큐, 호출
visited[0][0] += 1
bfsQueue.append((0, 0))
bfs()
print(visited[n-1][m-1])
피드백
currentLocation은 튜플로, curY와 curX에 좌표를 나눠서 넣는다. 상하좌우 4번만 반복하면 되고, 다음 y, x가 어디로 갈 지 계산해주어야 한다. 이동하지 못하는 세 가지 경우를 생각할 줄 알아야 하고, visited[ny][nx]에 누적한 값 + 1을 넣어야 한다.
I mean