드디어 계절학기까지 끝이 났다..
전공공부때매 미루고 미뤘던 알고리즘 공부를 다시 시작했고, 영광스런 첫 BFS문제를 풀게되어 짧게 리뷰해보고자 한다.
우선, 문제는 아래와 같다.
문제
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
우선 문제를 보니 몇 가지 캐치할 수 있는 부분은
- 항상 출발 지점은 (1, 1)이고 도착 지점은 (N, M)이다.
- 주어진 배열을 간단하게 풀어보면 상, 하, 좌, 우 네 방향으로만 움직일 수 있다. (위의 경우 답이 15이므로..)
- 1인 곳으로만 이동할 수 있다.
우선 최단거리라는 키워드와 이동 비용(가중치)의 값이 1로 동일하므로 BFS 알고리즘을 사용하면 된다는 것을 쉽게 알아차릴 수 있다.
근데, 여기서 꽤 당황스러운 요구 사항이 발생했는데 바로 맵을 표현하는 각각의 수들이 붙어서 입력된다는 것이다.
어려운 문제는 아니지만 이렇게도 요구하는구나~ 싶었던 부분이다.
아무튼! 상하좌우 네 방향을 구현한 int형 배열 두 개와, 필요할 것 같은 변수들을 선언해준다.
int N, M, y, x;
int maps[104][104], visited[104][104];
queue<pair<int, int>> q;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};BFS를 구현하기 위해 필요한 큐까지 선언해주었으면 바로 아래에 코드를 작성해보겠다.
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
string lines;
cin >> lines;
for (int j = 0; j < M; j++) {
maps[i][j] = lines[j] - '0';
// scanf("%1d", maps[i][j]);
}
}
q.push({0, 0});
visited[0][0] = 1;
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 (!maps[ny][nx]) continue; // 항상 오버플로우 먼저
if (visited[ny][nx]) continue;
visited[ny][nx] = visited[y][x] + 1;
q.push({ny, nx});
}
}
cout << visited[N - 1][M - 1];
}우선 나는 붙어있는 숫자를 string으로 입력받은 다음 for문 안에서 인덱스에 따라 하나씩 접근하였다.
나중에 강의를 보고 알게된 사실이지만 주석처리한 것처럼 scanf를 사용하면 더 간단하게 따닥따닥 붙어있는 것들을 처리할 수 있다..(정답을 맞춰도 강의를 봐야하는 이유임)
맵을 전부 입력받으면 바로 큐에 출발 좌표인 (0, 0)을 삽입한다.
while문 안에 있는 for문은 기존 좌표에서 상하좌우 네 방향으로 움직이면서 탐색하는 과정을 나타내는 것인데 그 아래에 있는 if문이 매우 중요하다.
만약 위 세 개의 if문에서 오버플로우와 언더플로우를 먼저 검사하지 않고 방문 여부나 0인 곳을 탐색하는 조건을 먼저 적용하게 되면 어떻게 될까?
아마 인덱스가 범위를 넘어서는 경우에 대한 처리가 이루어지기 전에 범위 외의 배열에 참조하려고 하기 때문에 segmentation fault가 일어날 것이다.
그렇기 때문에 항상 범위의 유효성을 먼저 체크해주어야 하는 것을 명심하자!
위 문제는 그냥 BFS 알고리즘만 사용하면 쉽게 풀리는 문제였지만 if문의 조건 처리와 scanf로 따닥따닥 붙어있는 맵을 입력받을 수 있다는 점을 새롭게 알게되어서 이렇게 블로그에 적어 보았다!
