[백준] 2178번: 미로 탐색

🔍 문제 읽기

2178번: 미로 탐색

입력	출력
N과 M N x M 미로의 정보 (입력이 붙어서 들어온다!)	(1, 1) ~ (N, M)까지 이동할 때, 지나야하는 최소의 칸 수
4 6 101111 101010 101011 111011	15

 

 

출발점과 도착점은 지정된다. 단순히 출발점에서 도착점까지의 최단거리를 찾는 문제다.

항상 도착위치로 이동할 수 있는 경우만 입력된다.

 

 

 

 

💡풀이 

👩‍💻 사용언어 : cpp

 

 

아래 두 가지가 문제 풀이에서 핵심이 된다.

❗️[핵심] 다차원 배열에서의 BFS (너비 우선)

👉 BFS는 너비 우선이기에 최단거리를 구할 수 있다.

👉 같은 유형인 1926번: 그림에서는 방문여부를 확인하는 배열(vis)을 사용했으나,

이 문제에서는 거리를 저장할 배열(dist)을 사용한다.

dist는 ①방문 여부와 ②거리를 저장하는 두가지 역할을 한다.

 

💡방문 여부를 사용하는 배열(vis)을 다룰 때는

👉 방문 O ➡︎ 1

👉 방문 X ➡︎ 0

 

💡거리를 저장하는 배열을 -1로 초기화한다.

👉 방문 X ➡︎ -1

👉 방문 O ➡︎ -1이 아닌 출발점으로 부터 거리 값 저장

 

❗️공백 없이 입력이 들어올 때

👉 string 배열을 사용해 입력 받는다.

 

 

 

🧩 코드

출발점을 1로 지정해 방문 여부와 거리를 지정한다.

입력받은 board 배열의 자료형이 string인 점을 잊지 말자.