[구름LEVEL] 미로찾기

난이도	정답률
★★★★	-%

프리미엄 알고리즘 위클리 비타알고 시즌3 3월 2주차

goorm

문제

N*N 크기의 격자판의 (1,1)에서 출발하여 (N,N)까지 이동하고자 한다. 미로는 0부터 9까지의 정수로 표현할 수 있으며 각각의 정수는 다음을 뜻한다.

• 0: 이동할 수 있는 통로
• 1: 벽
• 2...9: 워프를 할 수 있는 발판, 같은 번호의 발판끼리 이동 가능 

2번 부터 9번까지는 격자판에 항상 2개 이상 존재하며, 각 칸을 이동하는 시간과 워프를 하는 시간은 모두 1초 걸린다.

미로를 탈출하기 위해 걸리는 최소 시간을 구해보자.

시행착오

DFS로 접근했다가 7개의 테케에서 runtime error나서 DP로 바꿨더니 무려 90점을 맞았었다.(7번 테케만 틀림)

정말 모르겠어서 해설을 보니까 BFS였다. 그래서 다시 BFS로 짜보니 나는 또 3개만 맞고 7개의 테케에서 runtime error였다. 여기서 내 코드가 분명 문제가 있었구나 싶어서 하나하나 다시 살펴봤는데, BFS할 때, 워프를 만나면 워프 먼저 queue에 넣어야하는데, 워프가 아닌 것 부터 넣어서... 그 순서만 바꾸니(BFS코드의 46, 47번 줄 순서만 바꿈) runtime error는 해결이 되었고 7번과 10번 테스트케이스만 틀리게 되었다. 띠용..😱

+ 200327 도착하지 못하는경우 -1로 출력하게 하니 7번 테케 하나만 틀리게됨.

계속 생각을 해봐도 이제는 더 이상 아이디어가 나오지 않는다ㅜ 일단 블로그에 올려두고 나중에 다시 풀어봐야겠다.

코드

DP : 위에서 아래로만 가니 맨 아래에서 다시 올라오는 케이스에서는 실패.

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> p;
int dx[] = { 0,1,0 }, dy[] = { 1,0,-1 };
int n, arr[1005][1005], dp[1005][1005];
vector<p> warp[10];
void goWarp(int x, int y, int warpNum) {
    for (auto e : warp[warpNum]) {
        p child = e;
        int nx = child.first, ny = child.second;
        if (nx == x && ny == y) continue;
        dp[nx][ny] = dp[nx][ny] == -1 ? dp[x][y] + 1 : min(dp[nx][ny], dp[x][y] + 1);
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] > 1) {
                warp[arr[i][j]].push_back({ i,j });
            }
        }
    }
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i][j] == -1) continue;
            for (int k = 0; k < 3; k++) {
                int nx = i + dx[k], ny = j + dy[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n || (dp[nx][ny] != -1 && dp[nx][ny] <= dp[i][j])) continue;
                if (arr[nx][ny] != 1) dp[nx][ny] = dp[i][j] + 1;
                if (arr[nx][ny] > 1) goWarp(nx, ny, arr[nx][ny]);
            }
        }
        for (int j = n - 1; j >= 0; j--) {
            if (dp[i][j] == -1) continue;
            for (int k = 0; k < 3; k++) {
                int nx = i + dx[k], ny = j + dy[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n || (dp[nx][ny] != -1 && dp[nx][ny] <= dp[i][j])) continue;
                if (arr[nx][ny] != 1) dp[nx][ny] = dp[i][j] + 1;
                if (arr[nx][ny] > 1) goWarp(nx, ny, arr[nx][ny]);
            }
        }
    }
    printf("%d", dp[n - 1][n - 1]);
    return 0;
}

 

BFS : int dx[] = { 0,1,0,-1 } 이어야 했다...

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> p;
int dx[] = { 0,1,0,1 }, dy[] = { 1,0,-1,0 };
int n, arr[1005][1005], chk[1005][1005], warpChk[10], ans;
vector<p> warp[10];
queue<p> q;
void warpPush(int x, int y, int warpNum) {
    warpChk[warpNum] = 1;
    for (auto e : warp[warpNum]) {
        p child = e;
        int time = chk[x][y], nx = child.first, ny = child.second;
        if (nx == x && ny == y) continue;
        chk[nx][ny] = time + 1;
        q.push({ nx, ny });
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] > 1) {
                warp[arr[i][j]].push_back({ i,j });
            }
        }
    }
 
    chk[0][0] = 1;
    q.push({ 0, 0 });
    while (!q.empty()) {
        p front = q.front();
        q.pop();
        int x = front.first, y = front.second;
        int time = chk[x][y];
        if (x == n - 1 && y == n - 1) {
            break;
        }
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || arr[nx][ny] == 1 || chk[nx][ny] || warpChk[arr[nx][ny]]) continue;
            chk[nx][ny] = time + 1;
            if (arr[nx][ny] > 1) { warpPush(nx, ny, arr[nx][ny]); }
            q.push({ nx, ny });
        }
    }
    printf("%d", chk[n - 1][n - 1] ? chk[n - 1][n - 1] : -1);
    return 0;
}

200327 추가

deque를 이용해서 해보니까 80점맞음.. 느낌 좋았는데 까비ㅜ

204002 추가

5 
0 1 0 0 0 
0 1 0 1 0  
0 1 0 2 0 
0 1 0 0 0  
0 0 0 2 0 

인 경우 11이 나와야 하는데 12가 나오고 있었음.(워프 우선 탐색 때문에)

그래서 아래 조건문에 (chk[nx][ny] && chk[nx][ny] <= chk[x][y]) 이 조건을 줬더니 답은 맞지만, 시간초과났다. 그래서 덱으로는 못 푸는 문제인 것 같고 그냥 BFS 큐 이용해서 돌리는 게 편한 것 같다.

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
typedef pair<int, int> p;
int dx[] = { 0, 1, 0,-1 }, dy[] = { 1, 0, -1, 0 };
int arr[1005][1005], chk[1005][1005], warpChk[10];
int n;
vector<p> warp[10];
deque<p> dq;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] > 1) {
                warp[arr[i][j]].push_back({ i, j });
            }
        }
    }
 
    chk[0][0] = 1;
    dq.push_back({ 0,0 });
    while (dq.size()) {
        auto front = dq.front();
        dq.pop_front();
        int x = front.first, y = front.second;
        if (x == n - 1 && y == n - 1) {
            printf("%d", chk[x][y]);
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || chk[nx][ny] || arr[nx][ny] == 1) continue;
            chk[nx][ny] = chk[x][y] + 1;
            if (arr[nx][ny] && !warpChk[arr[nx][ny]]) { // 워프이고 방문하지 않은 워프면
                warpChk[arr[nx][ny]] = 1;
                for (auto child : warp[arr[nx][ny]]) {
                    int cx = child.first, cy = child.second;
                    if (cx == nx && cy == ny) continue;
                    chk[cx][cy] = chk[nx][ny] + 1;
                    dq.push_front({ cx, cy });
                }
            }
            else {
                dq.push_back({ nx, ny });
            }
        }
    }
    printf("-1");
    return 0;
}

 

성공!!

 

해결

key point, int dx[] = { 0,1,0, -1 }, dy[] = { 1,0,-1, 0 }; 위쪽도 방문해야 한다는 사실!!!

1. 입력을 받다가 워프를 만나면, 워프번호에 맞는 행에 인자로 좌표를 저장한다.
2. 초기값( chk[0][0]=1, q.push({0,0}) )을 설정한다.
3. chk배열의 쓰임은 
   1. 방문을 했다면 1이상이고 
   2. 방문하지 않았다면 0이다.
   3. chk[i][j]의 값은 (i, j)를 방문하는 최소시간이다. 
4. BFS를 돈다.
5. 현재 위치는 x, y이고, 인접한 네 방향은 nx, ny이다.
6. 인접한 곳에 대해서 N*N 범위를 넘어가거나, 벽이거나, 방문했거나, 이미 방문한 워프라면 더 이상 확인하지 않는다.
7. 그 외의 경우에는 방문을 해야하므로 chk[nx][ny]을 현재시간+1로 저장한다.
8. 그런데 (nx, ny)위치가 워프라면
   1. 해당 워프번호에 대해서 방문했음을 알리고 → warpChk
   2. (현재 워프위치 제외)같은 워프번호를 가진 모든 위치에 대하여, 시간을 설정하고, 좌표를 q에 넣어준다.
9.  (nx, ny)위치가 워프가 아니라면, 확인할 거 없이 q에 넣어준다.
10. 위의 순서를 반복하다가 x가 n-1이고, y가 n-1이라면 탈출구이므로 반복문을 종료하고 현재시간을 출력한다.
11. 만약 탈출할 수 없다면 -1을 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> p;
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
int n, arr[1005][1005], chk[1005][1005], warpChk[10];
vector<p> warp[10];
queue<p> q;
void warpPush(int x, int y, int warpNum) {
    warpChk[warpNum] = 1;
    for (auto child : warp[warpNum]) {
        int time = chk[x][y], cx = child.first, cy = child.second;
        if (cx == x && cy == y) continue;
        chk[cx][cy] = time + 1;
        q.push({ cx, cy });
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] > 1) {
                warp[arr[i][j]].push_back({ i,j });
            }
        }
    }
    chk[0][0] = 1;
    q.push({ 0, 0 });
    while (!q.empty()) {
        p front = q.front();
        q.pop();
        int x = front.first, y = front.second;
        int time = chk[x][y];
        if (x == n - 1 && y == n - 1) {
            break;
        }
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || arr[nx][ny] == 1 || chk[nx][ny] || warpChk[arr[nx][ny]]) continue;            
           chk[nx][ny] = time + 1;
            if (arr[nx][ny] > 1) { warpPush(nx, ny, arr[nx][ny]); }
            else q.push({ nx, ny });
        }
    }
    printf("%d", chk[n - 1][n - 1] ? chk[n - 1][n - 1] : -1);
    return 0;
}
 

 

후기

시행착오의 BFS 코드에서 dx마지막 인자를 -1로 수정해주면 성공이었다.. 윽!!
DP로 바꿔풀다가 -1이 필요하지 않을 것 같아서 뺐었는데.... dp에도 필요했나보다?

+ 수정해봤는데 계속 7번이 틀림.. 나중에 고쳐야지 ㄱ-

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> p;
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
int n, arr[1005][1005], dp[1005][1005], warpChk[10];
vector<p> warp[10];
 
void goWarp(int x, int y, int warpNum) {
    for (auto child : warp[warpNum]) {
        int nx = child.first, ny = child.second;
        if (nx == x && ny == y) continue;
        dp[nx][ny] = dp[nx][ny] == -1 ? dp[x][y] + 1 : min(dp[nx][ny], dp[x][y] + 1);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] > 1) {
                warp[arr[i][j]].push_back({ i,j });
            }
        }
    }
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i][j] == -1) continue;
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k], ny = j + dy[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n || arr[nx][ny] == 1 || (dp[nx][ny] != -1 && dp[nx][ny] <= dp[i][j]) || warpChk[arr[nx][ny]] ) continue;
                dp[nx][ny] = dp[i][j] + 1;
                if (arr[nx][ny] > 1) goWarp(nx, ny, arr[nx][ny]);
            }
        }
        for (int j = n - 1; j >= 0; j--) {
            if (dp[i][j] == -1) continue;
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k], ny = j + dy[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n || arr[nx][ny] == 1 || (dp[nx][ny] != -1 && dp[nx][ny] <= dp[i][j]) || warpChk[arr[nx][ny]]) continue;
                dp[nx][ny] = dp[i][j] + 1;
                if (arr[nx][ny] > 1) {
                    goWarp(nx, ny, arr[nx][ny]);
                    warpChk[arr[nx][ny]] = 1;
                }
            }
        }
    }
    printf("%d", dp[n - 1][n - 1]);
    return 0;
}
 

deque으로 푼 방법은.. 음.... 올치않은 방법인것 같다!

+ 200401 질문남겨서 답변을 받았는데

5
0 1 0 0 0
0 1 0 1 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0

위와 같은 경우에 내 dp코드로 풀었을 경우 (4, 2)에서 더 이상 위로 올라갈 수 없으므로 -1을 출력하게 된다.

다양한 테스트케이스에 대해서 생각해볼줄 알았다면 간단히 해결했을 것 같다.

+ 200402 덱도 반례를 찾아서 워프를 앞에 넣으면 안된다는 것을 발견했다. 그럴거면 그냥 편하게 큐를 쓰자!