BFS는 너비 우선 탐색으로 인접해있는 가까운 노드를 먼저 탐색하는 알고리즘이다.
BFS 이론은 어느정도 이해 했는데 코드를 어떻게 짜라는거지?.. 에 대한 의문이 계속 남았다.
큰돌님 블로그의 BFS 예시 문제로 공부했다.
이해가 안가지만.. 최대한 이해해보려고 정답 코드를 먼저 살펴보면서 한줄한줄 해석하기로 했다.
제대로 작성했다고 생각했는데 출력 결과가 이상해서 디버깅하는 도중 문제와 예제 입력을 헷갈려서 작성했던 것 같다. (예제 입력 순서대로 입력을 받게 변경했더니 정상적으로 동작한다.)
N과 M이 주어진 다음에 N * M의 맵이 주어지고,
그 다음줄에 승원이의 위치, 당근마킷의 위치가 주어진다는 문제의 말대로 순서를 작성했는데
예제 입력에서는 N M 다음에 맵이 오는 게 아니라, 승원이Y,X 당근마킷Y,X 그리고 N*M맵 순서로 주어지고 있었다.
그런데 뭔가 코드를 잘못 따라갔나보다.
육지가 아닌 바다까지 전부 카운트가 되어버렸다.
나중에 자바스크립트 코드로 작성해보면서 알게되었는데 바다인 경우엔
continue하도록 해야 되는데 예외 처리를 하지 않았다는 것을 발견했다.
큰돌님 코드로 해보니 visited를 디버깅했을 때 이렇게 나와야 한다.
#include <bits/stdc++.h>
using namespace std;
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1};
int land[104][104] = {0,};
int visited[104][104] = {0,};
int N, M;
int y, x; // 승원
int my, mx; // 당근
int main(){
cin >> N >> M >> y >> x >> my >> mx;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> land[i][j];
}
}
queue<pair<int, int>> q;
visited[y][x] = 1;
q.push({y, x});
while(q.size()){
tie(y, x) = q.front(); q.pop();
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
if(visited[ny][nx]) continue;
visited[ny][nx] = visited[y][x] + 1;
q.push({ny, nx});
}
}
cout << visited[my][mx] << "\n"; // 당근 개수
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cout << visited[i][j] << " ";
}
cout << "\n";
}
return 0;
}
핵심 코드 부분인 queue는 나에겐 너무 생소해서 이번에 코드 따라 작성해보면서 처음 사용해봤다.
메인 로직
queue<pair<int, int>> q;
visited[y][x] = 1;
q.push({y, x});
while(q.size()){
tie(y, x) = q.front(); q.pop();
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
if(visited[ny][nx]) continue;
visited[ny][nx] = visited[y][x] + 1;
q.push({ny, nx});
}
}먼저, 2쌍(y와 x)을 저장할 수 있는 queue를 하나 만든다.
그 다음에 방문했던 곳을 또 방문하지 않도록 처음 승원이의 위치인 0, 0 지점인 visited 배열[0][0] 번째의 값을 1로 변경시켜준다.
그리고 큐에 y와 x를 묶어 담는다.
방향벡터를 사용해서 현재 위치를 기준으로 상하좌우 이동을 해서 방문하지 않았으면서 육지인 곳을 반복적으로 확인해야하므로 while문을 사용한다.
큐의 사이즈가 0이 되면 반복문이 종료될 수 있도록 while문의 조건에 큐의 size를 넣어주었다.
큐에는 현재 위치가 담겨있는데 while문에 들어가게 되면 큐의 가장 첫번째에 있는 것을 꺼내오고 큐에서 제거시킨다.
그리고 4방향 벡터 for문을 돌면서 이미 방문했었는지, 맵의 범위를 초과하는지, 바다가 아닌지(육지인지) 확인하고 그렇지 않을 때만 방문처리를 해준다.
★ 중요! ★ 단, 방문 처리를 할 때는 이전 방문 값에서 1을 증가시킨 값을 visited 배열에 저장시킨다.
이후 큐에 방금 전에 방문처리한 y와 x를 담고 반복시킨다.
자바스크립트로 다시 풀어보기!
// 전체 맵
const landAndSea = [
[1, 0, 1, 0, 1],
[1, 1, 1, 0, 1],
[0, 0, 1, 1, 1],
[0, 0, 1, 1, 1],
[0, 0, 1, 1, 1]
];
// 방문 처리할 배열
const visited = Array(landAndSea.length)
.fill([])
.map(() => Array(landAndSea[0].length).fill(0));
// 이동 방향
const y = [-1, 0, 1, 0];
const x = [0, 1, 0, -1];
// 승원이 위치
let sy = 0;
let sx = 0;
// 당근마킷 위치
let my = 4;
let mx = 4;
const q = [];
visited[sy][sx] = 1;
q.push([sy, sx]);
while (q.length) {
let [cy, cx] = q.shift();
for (let i = 0; i < 4; i++) {
let ny = cy + y[i];
let nx = cx + x[i];
if (
ny < 0 ||
nx < 0 ||
ny >= landAndSea.length ||
nx >= landAndSea[0].length
)
continue;
if(landAndSea[ny][nx] === 0) continue;
if (visited[ny][nx]) continue;
visited[ny][nx] = visited[cy][cx] + 1;
q.push([ny, nx]);
}
}
console.log(visited[my][mx]); // 당근 개수
/* 디버깅용 */
for (let i = 0; i < visited.length; i++) {
console.log(visited[i]);
}
와 댑악 완전 신기...ㅋㅋㅋ
최단거리 나오는거 짱신기........
c++로 베껴보면서 이해하고 이해한 바를 토대로 자바스크립트로 재작성하니 조금 더 이해하기 쉬웠다!
아직 완벽하게 BFS 코드를 다루지는 못하는 것 같아서 시간이 좀 지나서 까먹지 않았을까 싶을 때 다시 이 문제를 풀어봐야겠다!
참고 자료
큰돌의 터전
