[구름LEVEL] 벽 통과하기

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

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

goorm

문제

 

해결

key point, 방문한 시각이 작은 곳을 우선적으로 방문한다. priority_queue

1. 우선순위 큐에 방문한 시각과 좌표를 저장한다. → {time, {x, y}}
2. 현재 보고있는 위치와 인접한 곳을 확인하면서
   1. 벽이 있다면 시간은 그대로, 좌표만 다음 위치에 맞춰 넣어준다.
   2. 벽이 없다면 시간은 +1, 다음 위치 좌표를 넣어준다.
3. 이렇게 순차적으로 순회하다보면 N,N 위치에 도달하게 되고 그 때의 time을 출력하면 최소 시간이 된다.

 

코드

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> p;
int n, ans = 1e9;
int dx[] = { 0,1,0, -1 }, dy[] = { 1,0,-1, 0 };
int arr[1005][1005], chk[1005][1005];
priority_queue<pair<int, p>, vector<pair<int, p>>, greater<pair<int, p>>> pq;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    chk[0][0] = 1;
    pq.push({ 1, {0,0} });
    while (!pq.empty()) {
        pair<int, p> front = pq.top();
        pq.pop();
        int time = front.first, x = front.second.first, y = front.second.second;
        if (x == n - 1 && y == n - 1) {
            printf("%d", time - 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 || chk[nx][ny]) continue;
            if (arr[nx][ny]) {
                chk[nx][ny] = time;
                pq.push({ time, { nx, ny } });
            }
            else {
                chk[nx][ny] = time + 1;
                pq.push({ time + 1, { nx, ny } });
            }
        }
    }
    return 0;
}

 

deque사용

이전에 덱은 전혀 사용해본 적이 없어서 우선순위 큐를 사용해서 문제를 풀었던건데, 해설을 확인해보니 덱을 사용하고 있어서 저도 덱을 이용해서 다시 풀어봤습니다.

#include <iostream>
#include<deque>
using namespace std;
typedef pair<int, int> p;
int arr[1005][1005], chk[1005][1005];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0};
deque<p> dq;
int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &arr[i][j]);
 
    dq.push_back({ 0, 0 });
    chk[0][0] = 1;
    while (dq.size()) {
        auto cur = dq.front();
        int x = cur.first, y = cur.second;
        dq.pop_front();
        if (x == n - 1 && y == n - 1) {
            printf("%d", chk[x][y] - 1);
            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]) continue;
            if (arr[nx][ny]) {    //다음 방문해야 할 곳이 벽이라면 덱의 앞에 정점을 넣어줌
                chk[nx][ny] = chk[x][y];
                dq.push_front({ nx, ny });
            }
            else {    //다음 방문해야 할 곳이 벽이 아니라면 덱의 뒤에 정점을 넣어줌
                chk[nx][ny] = chk[x][y] + 1;
                dq.push_back({ nx, ny });
            }            
        }
    }
}