[알고리즘/BFS] 14940번 : 쉬운 최단거리 - python

링크 : https://www.acmicpc.net/problem/14940

 

 

 

---

• 문제
• 소요시간: 34분 11초

---

• 설계하기(접근방법) 

1. 입력받기 

배열을 입력받는다

 

2. 구현하기

지도와 visited 배열을 선언해준다

 

for문을 통해 시작지점(2)를 찾아주어 저장한다

 

bfs를 순횐하면서 벽(0)인 경우 continue

아니라면 visited에 가중치를 저장해나간다

 

이동 가능 공간이지만, 벽에 가로막혀서 이동하지 못한경우

map과 visited를 비교하여 -1로 저장해준다

 

 

3. 출력하기

출력해준다

 

---

• 코드(출력)

import sys
from collections import deque

input = sys.stdin.readline

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

mapp = []
visited = [[0 for _ in range(m)] for _ in range(n)]


for i in range(n):
    mapp.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if mapp[i][j] == 2:
            start = [i,j]
            break

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

def bfs(start_x, start_y):
    q = deque()
    q.append([start_x, start_y])

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0<= ny < m:
                if mapp[nx][ny] == 1 and visited[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append([nx,ny])

bfs(start[0], start[1])

for i in range(n):
    for j in range(m):
        if mapp[i][j] == 1 and visited[i][j] == 0:
            visited[i][j] = -1


for i in visited:
    print(*i)

---

• 얻어갈 부분

1. 이동이 불가능한 경우의 조건을 빼먹어서 10분정도 더 낭비했다. 요구사항을 좀 더 꼼꼼히 읽자