반응형
https://www.acmicpc.net/problem/14940
14940번: 쉬운 최단거리
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이
www.acmicpc.net
소스코드
풀이
★ 전형적인 BFS 문제입니다. 목표지점이라고 해서, 거기까지 가는 거리를 구하는 것이 아닌 목표지점으로부터 각각의 땅이 얼마만큼 떨어진 위치에 있는지 확인해주면 됩니다 :)
★ 거리를 측정하는 그래프인 visited 배열을 -1로 초기화 해줍니다. -1로 초기화하는 이유는 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력해야 하기 때문입니다.
★ 그래프의 목표지점부터 시작해 상하좌우를 탐색하며, 갈 수 있는 땅 즉, 그래프 상의 좌표가 1인 곳으로 이동합니다. 할 때, 자신이 가지고 있던 좌표 값에 1씩 더하여 줌으로써 이동함을 체크할 수 있습니다 !
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 1655번: 가운데를 말해요 (Python) (1) | 2023.10.27 |
|---|---|
| [백준 알고리즘] 2231번: 분해합 (Python) (0) | 2023.10.26 |
| [백준 알고리즘] 1253번: 좋다 (Python) (1) | 2023.10.23 |
| [백준 알고리즘] 24479번: 알고리즘 수업 - 깊이우선탐색 1 (Python, DFS) (0) | 2023.10.20 |
| [백준 알고리즘] 1431번: 시리얼 번호 (Python) (1) | 2023.10.20 |