겉보기에는 그냥저냥 무난한 난이도의 그래프 탐색 문제다.
최소 탐색시간을 찾아내는 문제라, BFS 로 접근해야하는 명확성이 보였다.
하지만 약간 애를 먹었던 부분은 내가 방문 배열을 3차원이 아닌 2차원으로 설정했다는 것이다.
완성 코드를 살펴보자.
#include<iostream>
#include<queue>
using namespace std;
int N, M;
int T;
int map[101][101];
int visit[101][101][2];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
struct node {
int x;
int y;
int time;
bool sword;
};
queue<node> q;
void input() {
cin >> N >> M >> T;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> map[i][j];
}
}
}
void bfs() {
q.push({ 1, 1, 0, false });
visit[1][1][0] = 1;
while (!q.empty()) {
int px = q.front().x;
int py = q.front().y;
int time = q.front().time;
bool state = q.front().sword;
q.pop();
if (time > T) {
cout << "Fail" << endl;
return;
}
if (px == N && py == M) {
cout << time << endl;
return;
}
for (int i = 0; i < 4; i++) {
int nx = px + dx[i];
int ny = py + dy[i];
if (nx < 1 || ny < 1 || nx > N || ny > M) continue;
if (state == true ) {
if (visit[nx][ny][1] == 0) {
visit[nx][ny][1] = 1;
q.push({ nx, ny, time + 1, true });
}
}
else {
if (map[nx][ny] == 2 && visit[nx][ny][0] == 0) {
visit[nx][ny][0] = 1;
q.push({ nx, ny, time + 1, true });
}
else if (map[nx][ny] == 0 && visit[nx][ny][0] == 0) {
visit[nx][ny][0] = 1;
q.push({ nx, ny, time + 1, false });
}
}
}
}
cout << "Fail" << endl;
return;
}
int main() {
input();
bfs();
}예시 데이터를 넣고 코드를 돌렸을 때 제대로 된 값이 나오지 않았던 이유는 바로 내가 visit 배열을 2차원으로 설정했기 때문이였다. 즉, 칼을 가진 경우와 칼을 가지지 않은 경우를 나누어 방문 배열을 탐색해야 한다는 의미다. 같은 좌표인데 왜 칼을 가진 경우와 가지지 않은 경우를 나누어야 할까? 케이스를 나누는 것이 최소 거리를 구하는 로직에 영향을 끼칠까?
예를 들어, 칼을 가지고 있지 않은 상태로 특정 노드를 방문한 후, 칼을 가진 상태로 또 한번 방문해도 된다는 뜻이다. 사실 이전에도 비슷한 문제로 머리가 복잡했던 경험이 있다. 이동하는 방식이 나뉜다고 해서, 왜 방문 배열의 케이스를 늘려야 하는지 명확하게 와닿지 않았다. 언뜻 생각하기에는 시간 정보가 함꼐 들어가는 큐의 특성상 어차피 가장 먼저 들어가는 좌표가 최단거리가 아닐까.. 하는 그런 생각이다.
이는 예시를 들어 생각하면 머리가 아프다. 사실 이유는 간단하다.
최단 거리의 상태가 검을 얻었을 때 / 검을 얻지 않았을 때 로 나뉘기 때문이다.
이게 무슨 당연한 소리인가 싶겠지만, 당연한 소리를 당연하게 받아들이는게 중요한 것 같다.
검을 얻었을 때의 최단경로를 구하는 로직이 검을 얻지 않았을 때의 최단경로를 구하는 로직을 침범해서는 안되는 것은 당연한 것이고, 이를 분리하지 않으면 내가 알지 못하는 반례 상황이 반드시 생기기 마련이다. 앞으로 명심하도록 하자.
또 하나 괜찮은 습관을 찾아낸 것 같은데,
if (time > T) {
cout << "Fail" << endl;
return;
}
if (px == N && py == M) {
cout << time << endl;
return;
}시간 초과를 판별하는 로직과 시간을 출력하는 로직을 한번에 짜지 않고, 일차적으로 시간 초과를 판별한 후 좌표를 검증하고 시간을 출력하는 방향이 깔끔하다는 생각이다.
