20시즌 서주연이 코딩에 손을 놓아버리게 만든 그 문제
문제 2206
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
예제 입력 1
6 4
0100
1110
1000
0000
0111
0000예제 출력 1
15
예제 입력 2
4 4
0111
1111
1111
1110예제 출력2
-1풀이
사실 예전에 이미 풀었던 이 문제를 다시 리뷰하는 이유는 <벽 부수고 이동하기> 시리즈를 모조리 박살내기 전에 하는 일종의 몸풀기라 볼 수 있다. 예나 지금이나 문제를 읽어봤을 때 도저히 감이 안잡히는 건 마찬가지다. 2년이 지났는데... 부끄러운 줄 알고 반성하자.
문제의 해결법은 간단하다. visited 배열의 차원을 한 단계 올리는 것이다. 자세한 풀이는 구글에잘 나와있다. 0의 세계, 1의 세계 어쩌구하는 풀이가 굉장히 인상깊었는데 오랜만에 다시 찾아보려니 못찾겠다 까비 ㅋㅋ
코드
#include <iostream>
#include <queue>
#define MAX_SCOPE 1001
#define isVisited 1
#define notVisited 0
#define isBroken 1
#define notBroken 0
#define ALL_BROKEN 2
#define wall 1
#define road 0
#define ALL_DIR 4
using namespace std;
typedef struct {
int x;
int y;
int step;
int broken;
} coordinate;
int moveX[ALL_DIR] = {0, 1, 0, -1};
int moveY[ALL_DIR] = {-1, 0, 1, 0};
int n, m;
int map[MAX_SCOPE][MAX_SCOPE];
int visited[ALL_BROKEN][MAX_SCOPE][MAX_SCOPE] = {notVisited, };
int isArrived = 0;
queue<coordinate> q;
void init() {
cin >> n >> m;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
scanf("%1d", &map[i][j]);
}
}
}
void bfs() {
while(!q.empty()) {
coordinate cur = q.front();
// cout << "위치: " << cur.x << cur.y << endl;
q.pop();
if(cur.x == m-1 && cur.y == n-1) {
cout << cur.step << endl;
isArrived = 1;
break;
}
int nextX, nextY;
coordinate next;
for(int i = 0; i < ALL_DIR; i++) {
nextX = cur.x + moveX[i];
nextY = cur.y + moveY[i];
next.x = nextX;
next.y = nextY;
if(nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) {
if(cur.broken == isBroken && map[nextY][nextX] == road && visited[isBroken][nextY][nextX] == notVisited) {
next.broken = isBroken;
visited[isBroken][nextY][nextX] = isVisited;
next.step = cur.step + 1;
q.push(next);
}
else if(cur.broken == notBroken) {
if(map[nextY][nextX] == road && visited[notBroken][nextY][nextX] == notVisited) {
next.broken = notBroken;
visited[notBroken][nextY][nextX] = isVisited;
next.step = cur.step + 1;
q.push(next);
}
else if(map[nextY][nextX] == wall && visited[isBroken][nextY][nextX] == notVisited) {
next.broken = isBroken;
visited[isBroken][nextY][nextX] = isVisited;
next.step = cur.step + 1;
q.push(next);
}
}
}
}
}
if(isArrived == 0) {
cout << -1 << endl;
}
}
void solve() {
coordinate start;
start.x = 0;
start.y = 0;
start.step = 1;
start.broken = notBroken;
q.push(start);
visited[notBroken][0][0] = isVisited;
bfs();
}
int main() {
init();
solve();
}생각
우선 예전 코드를 보며 발전했다고 느낀 점
- 최근에는 그래프 문제를 풀 때 pair 사용을 지양하고 구조체를 사용하려 하고 있는데 메모리 면에서는 pair 사용이 조금 더 우수한 것 같다. 그러나 구조체를 사용하는 쪽이 가독성 면에서 훨씬 우수하기 때문에 왠만하면 앞으로도 구조체를 사용할 듯하다.
- 여러 사람들의 코드를 보며 bfs 함수의 body에 초기값을 넣는(맨 첫 push) 코드를 포함시키기로 했고, bfs 함수의 종료를 bool 변수로 판단하는 대신 return 해버리기로 했다.
입력 값이 붙어서 들어올 때는 이렇게 처리하는 방법이 있다는 사실을 잊지말자.
scanf("%1d", &arr[][]);문제 14442
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
예제 입력 1
6 4 1
0100
1110
1000
0000
0111
0000예제 출력 1
15예제 입력 2
6 4 2
0100
1110
1000
0000
0111
0000예제 출력 2
9예제 입력 3
4 4 3
0111
1111
1111
1110예제 출력 3
-1풀이
이전 문제에서 변화된 점은 부술 수 있는 벽이라는 의미로 K라는 변수가 추가되었다는 사실이다. 기존에는 오직 1개의 벽만 부술 수 있었으므로, K는 1인 문제였다고 볼 수 있다. 이전에는 visited 배열을 notBroken과 isBroken의 2차원으로 표현했다. 이 문제를 해결하기 위해서는 이 차원을 늘려주어야 한다는 생각이 들었다.
맨 처음에는 굳이 차원을 늘려주지 않고도 풀 수 있지 않을까하는 의문이 생겼다. 벽을 부순 횟수가 0~K-1에 해당하는 경우에는 notBroken 차원의 visited 배열을 사용하고 벽을 최대로 부순 경우에는 isBroken 차원의 visited 배열을 사용하면 되지 않나? 그래서 직접 코드를 짜봤다. 차원을 늘리지 않아도 되긴 했지만 벽을 부순 횟수가 K-1에서 K로 넘어가는 경우를 예외처리해주는게 조금 까다로웠다.
결과는 아쉽게도 오답이었다. 사실 어느 정도 예상하긴 했지만 풀이가 틀렸다는 걸 보여주는 마땅한 반례를 찾지 못해 마지못해 제출해봤다. 그렇다면 왜 오답인걸까?
내가 생각한 반례는 이러하다. 아직 벽을 최대한으로 부수지 못한 상태에서 어떠한 길 (Y,X)를 최초로 방문하여 notBroken 차원의 visited 배열을 방문처리하였다. 이때 brokenCount는 b이고, step은 s라고 하자. 만약 이런 식으로 방문 처리를 해버리면, 이후에 벽을 최대한으로 부수지 못한 상태에서 같은 길 (Y,X)를 재방문하지 못한다. 이때에는 step이 s보다 같거나 크겠지만 (BFS 이므로) brokenCount는 b보다 작을 수도 있으므로 이때의 방문이 결과적으로 더 짧은 경로를 낳을수도 있는 것이다.
코드
#include <iostream>
#include <queue>
#define MAX_SCOPE 1001
#define isVisited 1
#define notVisited 0
#define notBroken 0
#define ALL_BROKEN 11
#define wall 1
#define road 0
#define ALL_DIR 4
using namespace std;
typedef struct {
int x;
int y;
int step;
int brokenCount;
} coordinate;
int moveX[ALL_DIR] = {0, 1, 0, -1};
int moveY[ALL_DIR] = {-1, 0, 1, 0};
int n, m, maxBreak;
int map[MAX_SCOPE][MAX_SCOPE];
int visited[ALL_BROKEN][MAX_SCOPE][MAX_SCOPE] = {notVisited, };
queue<coordinate> q;
void init() {
cin >> n >> m >> maxBreak;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
scanf("%1d", &map[i][j]);
}
}
}
void bfs() {
coordinate start = {0, 0, 1, notBroken};
q.push(start);
visited[notBroken][0][0] = isVisited;
while(!q.empty()) {
coordinate cur = q.front();
q.pop();
if(cur.x == m-1 && cur.y == n-1) {
cout << cur.step << endl;
return;
}
int nextX, nextY;
coordinate next;
for(int i = 0; i < ALL_DIR; i++) {
nextX = cur.x + moveX[i];
nextY = cur.y + moveY[i];
next.x = nextX;
next.y = nextY;
if(nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) {
if(cur.brokenCount == maxBreak && map[nextY][nextX] == road && visited[maxBreak][nextY][nextX] == notVisited) {
next.brokenCount = cur.brokenCount;
visited[maxBreak][nextY][nextX] = isVisited;
next.step = cur.step + 1;
q.push(next);
}
else if(cur.brokenCount != maxBreak) {
if(map[nextY][nextX] == road && visited[cur.brokenCount][nextY][nextX] == notVisited) {
next.brokenCount = cur.brokenCount;
visited[next.brokenCount][nextY][nextX] = isVisited;
next.step = cur.step + 1;
q.push(next);
}
else if(map[nextY][nextX] == wall && visited[cur.brokenCount+1][nextY][nextX] == notVisited) {
next.brokenCount = cur.brokenCount + 1;
visited[next.brokenCount][nextY][nextX] = isVisited;
next.step = cur.step + 1;
q.push(next);
}
}
}
}
}
cout << -1 << endl;
}
void solve() {
bfs();
}
int main() {
init();
solve();
}생각
문제 해결법이 뻔하긴 했지만 오기가 생겨서 시간이 조금 걸렸다. 다차원의 visited 배열을 사용할 수 있다는 걸 항상 명심해두어야겠다.
문제 16933
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다.
이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.
만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 단, 벽은 낮에만 부술 수 있다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
예제 입력 1
1 4 1
0010예제 출력 1
5예제 입력 2
1 4 1
0100예제 출력 2
4예제 입력 3
6 4 1
0100
1110
1000
0000
0111
0000예제 출력 3
15예제 입력 4
6 4 2
0100
1110
1000
0000
0111
0000예제 출력 4
9풀이
문제를 읽는 게 상당히 흥미로웠다. 낮과 밤이라는 조건이 추가되고 이동하지 않고 같은 칸에 머무르는 옵션이 추가되었다. 맨 처음의 생각은 이렇다. 벽을 부수는 경우의 if문에 낮밤을 체크하는 부분을 추가했고, for 문으로 상하좌우를 체크하기 전에 제자리에 머무는 경우를 무조건 push해줬다. 그랬더니...?
두둥탁. 시간초과였다. 논리에 빵꾸가 나면 났지,,, 시간초과...? 로직 자체가 잘못된건가하는 생각이 들어 당황스러웠다. 일단 다시 코드를 보니 제자리에 머무는 경우를 무조건 push하는 부분이 매우 강력한 용의자로 의심되었다. 조금 생각해보니 매번 push를 한다는 게 얼마나 멍청한 생각인지 깨닫게 되었다 ㅋㅋ
우선 아침에는 벽을 부술 수 있기 때문에 제자리에 한 번 더 머물 필요가 없었다. (step만 1 추가되는 꼴이므로) 그렇기에 우선 밤인지 체크하는 if문을 넣어주었다. 그리고 다시 제출했지만 아쉽게도 또 시간초과. 조금 더 생각해보았다.
생각해보니 제자리에 있는 걸 고려해보는 경우는 현재는 밤이라 벽을 부수지 못하고 있지만 낮이 되어 벽을 부수면 더 짧은 거리로 이동할 수 있는 경우임을 깨달았다. 그래서 for 문으로 상하좌우를 체크해보면서 부수고 이동할 수 있는 벽이 있는 지를 체크해주었다. 그리고 다시 제출했더니 정답!
코드
#include <iostream>
#include <queue>
#define MAX_SCOPE 1001
#define isVisited 1
#define notVisited 0
#define notBroken 0
#define ALL_BROKEN 11
#define wall 1
#define road 0
#define ALL_DIR 4
#define day 0
#define night 1
using namespace std;
typedef struct {
int x;
int y;
int step;
int brokenCount;
int time;
} coordinate;
int moveX[ALL_DIR] = {0, 1, 0, -1};
int moveY[ALL_DIR] = {-1, 0, 1, 0};
int n, m, maxBreak;
int map[MAX_SCOPE][MAX_SCOPE];
int visited[ALL_BROKEN][MAX_SCOPE][MAX_SCOPE] = {notVisited, };
queue<coordinate> q;
void init() {
cin >> n >> m >> maxBreak;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
scanf("%1d", &map[i][j]);
}
}
}
void bfs() {
coordinate start = {0, 0, 1, notBroken, 0};
q.push(start);
visited[notBroken][0][0] = isVisited;
while(!q.empty()) {
coordinate cur = q.front();
q.pop();
if(cur.x == m-1 && cur.y == n-1) {
cout << cur.step << endl;
return;
}
int nextX, nextY;
coordinate next;
if(cur.time % 2 == night) { // 제자리에 있는 걸 고려해보는 경우
for(int i = 0; i < ALL_DIR; i++) {
nextX = cur.x + moveX[i];
nextY = cur.y + moveY[i];
if(nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) {
if(cur.brokenCount != maxBreak && map[nextY][nextX] == wall && visited[cur.brokenCount+1][nextY][nextX] == notVisited) { //제자리에 있어봐야 함
next.x = cur.x;
next.y = cur.y;
next.step = cur.step + 1;
next.brokenCount = cur.brokenCount;
next.time = cur.time + 1;
q.push(next);
break;
}
}
}
}
for(int i = 0; i < ALL_DIR; i++) {
nextX = cur.x + moveX[i];
nextY = cur.y + moveY[i];
next.x = nextX;
next.y = nextY;
if(nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) {
if(cur.brokenCount == maxBreak && map[nextY][nextX] == road && visited[maxBreak][nextY][nextX] == notVisited) {
next.brokenCount = cur.brokenCount;
visited[maxBreak][nextY][nextX] = isVisited;
next.step = cur.step + 1;
next.time = cur.time + 1;
q.push(next);
}
else if(cur.brokenCount != maxBreak) {
if(map[nextY][nextX] == road && visited[cur.brokenCount][nextY][nextX] == notVisited) {
next.brokenCount = cur.brokenCount;
visited[next.brokenCount][nextY][nextX] = isVisited;
next.step = cur.step + 1;
next.time = cur.time + 1;
q.push(next);
}
else if(map[nextY][nextX] == wall && visited[cur.brokenCount+1][nextY][nextX] == notVisited && cur.time % 2 == day) {
next.brokenCount = cur.brokenCount + 1;
visited[next.brokenCount][nextY][nextX] = isVisited;
next.step = cur.step + 1;
next.time = cur.time + 1;
q.push(next);
}
}
}
}
}
cout << -1 << endl;
}
void solve() {
bfs();
}
int main() {
init();
solve();
}생각
풀기 전에 난이도를 안봤는데 풀고 보니 골드 1...? (인생 첫 골드1 문제) 솔직히 좀 거품인 것 같다 ㅋㅋ 채점 결과가 시간 초과라 당황스럽긴 했는데 나름 잘 풀어나간 것 같다.
