궤도
[백준] 2206번 : 벽 부수고 이동하기 본문
문제
풀이
너어무 어려웠다. 골드 4길래 풀만할 줄 알았는데 아니었다. 반례가 너무 많았어서 기억도 안나고
여기서 더 최적화 할 수 있을 것 같은데 더 이상 못하겠다. 솔직히 설명도 잘할 자신이 없다.
먼저 난 처음에 기존에 미로찾기 처럼 input 배열을 갱신하는데 이제 벽을 부쉈는지 아닌지를 기록하면 될 것이라고 생각했다.
하지만 이 문제는 2차원 배열 하나로 간단하게 풀리는 문제가 아니었다.
이런 배열이 있다고 하자. 당시엔 matrix를 갱신할 생각이었어서 벽을 -1로 표현했다.
아직 벽을 부술 수 있는 상태는 파란색, 벽을 더이상 부실 수 없는 상태는 빨간색으로 표현했다.
좀 더 진행했다. 보라색은 벽을 부수고도, 안부수고도 갈 수 있음을 나타냈다.
아무튼 이렇게 벽을 부순 상태에서 갱신된 3, 4에 더이상 접근할 수 없어서 길이 있음에도 -1을 출력하는 것을 볼 수 있다.
그니까 돌아갈 수 있는 방법을 만들어야 한다.
matrix 배열에 더해 벽을 0개 부수며 방문한 곳을 기록한 배열과 벽을 1개 부수며 방문한 곳을 기록한 배열을 만들었다.
좀 더 진행해보도록 하겠다.
이 다음 단계가 중요하다. (3, 3)에 대해 상하좌우를 확인한다.
비록 matrix의 (3, 2)에는 4가 기록됐지만, 벽을 0개 부순 방문 배열을 봤을 때 (3, 2)는 아직 방문하지 않은 상태이다.
그렇기 때문에 (3, 2)를 5로 갱신할 수 있다.
다만 보라색으로 표시할 순 없는게 벽을 1개 부순 방문 배열의 (3, 2)는 이미 방문표시를 했기 때문이다.
어차피 똑같이 벽을 1개 부술거라면 4번만에 갈 수 있는걸 굳이 5로 갱신할 이유는 없기 떄문이다.
그래서 이렇게 갱신될 것이고
최종 모습은 이렇게 될 것이다. 사실 틀렸을 수도 있는데 논리는 맞으니까 봐주시길...
정리하자면
특정 좌표의 상하좌우에 대해 그 곳으로 갈 수 있는 방법은 크게 2가지 경우가 있다.
1. 길인 경우
2. 벽인 경우
1인 경우는 다시 이전까지 오면서 벽을 부순적 없는 경우와 벽을 부쉈던 경우로 나눌 수 있다.
벽을 부순적 없다면 파란색 visited 배열에 새로운 좌표의 방문표시를 한다.
벽을 부순적 있다면 빨간색 visited 배열에 새로운 좌표의 방문표시를 한다.
2인 경우 진행을 위해선 이전까지 벽을 부순적 없는 상태여야 한다.
그렇다면 기존 좌표의 방문표시가 파란색 visited 배열에 찍혀있었을 것,이고 새로운 좌표의 방문표시는 빨간색 visited 배열에 될 것이다.
그래서 난 이대로 matrix를 갱신하는 방법으로 코드를 짰는데...
계속 11%에서 틀렸다는 결과를 뱉어냈다. 결국 검색을 해보다가 matrix 배열을 갱신하지 않기로 했다....
기타 다른 반례들은 코드를 보면서 설명하겠다. 정답률이 20%대인 문제에는 이유가 있었다...
소스코드
#include <iostream>
#include <string>
#include <queue>
#include <utility>
using namespace std;
int N, M;
int matrix[1000][1000];
bool visited[1000][1000][2]; //0이면 벽 안부순 것, 1이면 벽 부순 것
struct state { //처음엔 matrix를 갱신했는데 틀렸다고 해서...
int row, col, crush, dist;
};
pair<int, int> dir[4] = {{-1, 0}, //상
{1, 0}, //하
{0, -1}, //좌
{0, 1}}; //우
int bfs(state start) { //큐로 구현
queue<state> q;
q.push(start);
while (!q.empty()) { //큐에 들어있는 모든 원소에 대해 가능한 방향 체크
int row = q.front().row;
int col = q.front().col;
int crush = q.front().crush;
int dist = q.front().dist;
if ((row == N - 1) && (col == M - 1)) //break 가능한지 확인
return dist;
q.pop();
for (int i = 0; i < 4; i++) {
int nr = row + dir[i].first;
int nc = col + dir[i].second;
if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < M) && //범위 체크
(matrix[nr][nc] == 0) && (visited[nr][nc][crush] == 0)) { //길을 만났을 때(이전에 벽을 부쉈을 수도 있고 아닐 수도 있음)
int nd = dist + 1;
visited[nr][nc][crush] = 1;
q.push({nr, nc, crush, nd});
} else if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < M) && //범위 체크
(crush == 0) && (matrix[nr][nc] == 1) && (visited[nr][nc][1] == 0)) { //벽을 안부순 상태에서 벽을 만났을 때
int nd = dist + 1;
visited[nr][nc][1] = 1;
q.push({nr, nc, 1, nd});
}
}
}
return -1;
}
int main() {
string tmp;
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> tmp;
for (int j = 0; j < M; j++) {
matrix[i][j] = tmp[j] - '0';
}
}
visited[0][0][0] = 1; //첫 시작은 벽을 부수지 않았으니까
state start = {0, 0, 0, 1};
cout << bfs(start);
}전체 소스코드고 개선할 수 있는 방법이 있겠지만 지금은 너무 지쳤기 때문에...
visited bool 배열과 dist를 합칠 수 있을 것 같긴 한데 지금은 하고 싶지 않다.
아무래도 내 수준에 맞지 않는 문제였던 것 같다.
int N, M;
int matrix[1000][1000];
bool visited[1000][1000][2]; //0이면 벽 안부순 것, 1이면 벽 부순 것
struct state { //처음엔 matrix를 갱신했는데 틀렸다고 해서...
int row, col, crush, dist;
};
pair<int, int> dir[4] = {{-1, 0}, //상
{1, 0}, //하
{0, -1}, //좌
{0, 1}}; //우방문 표시를 하는 visited 배열과 좌표의 상태를 기록하는 state 구조체가 중요하다.
만약 visited 배열을 확장하면 벽을 2번 부술 수 있는 경우 3번 부술 수 있는 경우...등을 기록할 수 있을 것이다. 난 생각하고 싶지 않다.
state 구조체에는 좌표의 행, 열과 부숨여부만을 저장했었는데 앞서 말했듯이 matrix 배열의 갱신을 실패해서 dist를 추가했다.
int main() {
string tmp;
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> tmp;
for (int j = 0; j < M; j++) {
matrix[i][j] = tmp[j] - '0';
}
}
visited[0][0][0] = 1; //첫 시작은 벽을 부수지 않았으니까
state start = {0, 0, 0, 1};
cout << bfs(start);
}처음 시작점은 벽이 없다고 했으니 벽을 부수지 않은 배열에 방문 표시를 한다.
시작점도 거리에 포함한다고 했으니 dist를 1로 하고 bfs를 호출한다.
int bfs(state start) { //큐로 구현
queue<state> q;
q.push(start);
while (!q.empty()) { //큐에 들어있는 모든 원소에 대해 가능한 방향 체크
int row = q.front().row;
int col = q.front().col;
int crush = q.front().crush;
int dist = q.front().dist;
if ((row == N - 1) && (col == M - 1)) //break 가능한지 확인
return dist;
q.pop();
for (int i = 0; i < 4; i++) {
int nr = row + dir[i].first;
int nc = col + dir[i].second;
if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < M) && //범위 체크
(matrix[nr][nc] == 0) && (visited[nr][nc][crush] == 0)) { //길을 만났을 때(이전에 벽을 부쉈을 수도 있고 아닐 수도 있음)
int nd = dist + 1;
visited[nr][nc][crush] = 1;
q.push({nr, nc, crush, nd});
} else if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < M) && //범위 체크
(crush == 0) && (matrix[nr][nc] == 1) && (visited[nr][nc][1] == 0)) { //벽을 안부순 상태에서 벽을 만났을 때
int nd = dist + 1;
visited[nr][nc][1] = 1;
q.push({nr, nc, 1, nd});
}
}
}
return -1;
}문제의 bfs 함수다...
int row = q.front().row;
int col = q.front().col;
int crush = q.front().crush;
int dist = q.front().dist;
if ((row == N - 1) && (col == M - 1)) //break 가능한지 확인
return dist;
q.pop();큐의 첫번째 원소를 빼내는 과정이다. 근데 이 때 이 원소가 혹시 우리의 도착점은 아닌지 확인해야 한다.
왜냐하면 괜히 벽을 부숴서 도착점까지 빠르게 도착했는데 큐가 비어있지 않아서 계속 값이 갱신되다가
벽을 부순적 없는 경로로 값이 갱신될 수도 있기 때문이다.
for (int i = 0; i < 4; i++) {
int nr = row + dir[i].first;
int nc = col + dir[i].second;
if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < M) && //범위 체크
(matrix[nr][nc] == 0) && (visited[nr][nc][crush] == 0)) { //길을 만났을 때(이전에 벽을 부쉈을 수도 있고 아닐 수도 있음)
int nd = dist + 1;
visited[nr][nc][crush] = 1;
q.push({nr, nc, crush, nd});
} else if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < M) && //범위 체크
(crush == 0) && (matrix[nr][nc] == 1) && (visited[nr][nc][1] == 0)) { //벽을 안부순 상태에서 벽을 만났을 때
int nd = dist + 1;
visited[nr][nc][1] = 1;
q.push({nr, nc, 1, nd});
}
}상하좌우에 대해 방문 가능을 체크하는 부분이다. 좀 더 자세하게 보면...
if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < M) && //범위 체크
(matrix[nr][nc] == 0) && (visited[nr][nc][crush] == 0)) { //길을 만났을 때(이전에 벽을 부쉈을 수도 있고 아닐 수도 있음)
int nd = dist + 1;
visited[nr][nc][crush] = 1;
q.push({nr, nc, crush, nd});
}이 경우는 새로운 좌표가 길인 경우이다.
만약 원래의 좌표가 벽을 부수지 않은 상황이었다면 똑같이 벽을 부수지 않은 상황에 값이 갱신될 것이다. (1)
반대로 원래의 좌표가 벽을 부순 상황이었다면 똑같이 벽을 부순 상황에 값이 갱신될 것이다. (2)
그러므로 상황에 따라 visited[nc][nr][0] == 0(1번 상황)이거나, visited[nc][nr][1] == 0(2번 상황)이어야 진행할 수 있다.
else if ((nr >= 0) && (nr < N) && (nc >= 0) && (nc < M) && //범위 체크
(crush == 0) && (matrix[nr][nc] == 1) && (visited[nr][nc][1] == 0)) { //벽을 안부순 상태에서 벽을 만났을 때
int nd = dist + 1;
visited[nr][nc][1] = 1;
q.push({nr, nc, 1, nd});
}이 경우는 새로운 좌표가 벽인 경우이다.
이럴 땐 원래의 좌표가 벽을 부순적 없는 상황이어야 하고 (cursh == 0)
이 새로운 좌표로 벽을 부숴서 방문한 적이 없어야 한다. (visited[nc][nr][1] == 0)
return -1;while문을 돌며 계속 break 가능 여부를 확인하니 while문을 문제없이 빠져나왔다면 길이 없는 것이다.
