728x90
쉬운 최단거리 성공
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 | 128 MB | 12940 | 5209 | 4230 | 37.832% |
문제
지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.
입력
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.
출력
각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.
예제 입력 1 복사
15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
예제 출력 1 복사
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34
너비우선 탐색 문제
시작점이 항상 고정이 아니기 때문에 , 배열을 받아올 때 문제에 나와있는대로 2를 탐색 후 위치를 넣어주고 BFS알고리즘을 적용해준다.
#14940 쉬운 최단거리
import sys
from collections import deque
n, m = map(int,sys.stdin.readline().split())
li = []
x,y = 0,0
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
for _ in range(n):
s = list(map(int,sys.stdin.readline().split()))
if 2 in s:
x,y = _,s.index(2)
li.append(s)
li[x][y] = 1
else:
li.append(s)
def BFS(x,y):
queue = deque()
queue.append((x,y))
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if li[nx][ny] == 0:
continue
if li[nx][ny] == 1:
li[nx][ny] = (li[x][y] + 1)
queue.append((nx,ny))
BFS(x,y)
for i in range(n):
for j in range(m):
if li[i][j] == 1:
li[i][j] = -1
elif li[i][j] != 0:
li[i][j] += -1
li[x][y] = 0
for i in range(n):
for j in range(m):
if li[i][j] != 0:
print(li[i][j],end=' ')
else:
print(0,end=' ')
print()
728x90
'Study > CodingTest' 카테고리의 다른 글
[백준/Python] (S3)2606 - 바이러스 (1) | 2023.12.08 |
---|---|
[백준/Python] (S2)1260 - DFS와 BFS (0) | 2023.12.07 |
[백준/Python] (S2)21736 - 헌내기는 친구가 필요해 (0) | 2023.07.27 |
[백준/Python] (G5)10026 - 적록색약 (0) | 2023.07.26 |
[백준/Python] (G5)5430 - AC (0) | 2023.07.25 |