백준 2665 미로만들기

작성일 | In |

Problem : 미로만들기

유형 : 다익스트라

문제 해석

  • 시작 방에서 끝방 까지 갈때, 최소로 바꾸는 검은 방의 개수를 구하라.

문제 재해석

  • 시작방과 끝방은 항상 흰색이다.
  • 숫자가 아닌 문자열로 입력이 들어온다.
  • 거리를 재는 것이 아닌, 바꾸는 방의 개수를 구한다.

해결 전략

  • 다익스트라를 이용하여 문제를 해결한다.
  • 바꾼 검은 방의 개수를 기준으로 min heap 으로 운영한다.

설계, 구현

  • 3개의 원소를 관리하여야 하니 구조체를 이용한다.
  • 구조체를 heap에 담으며 관리하니, 오버로딩을 통해 구조체를 만들어둔다.
  • 검은 방을 만난 경우, 일단 색을 바꿔버리고 들어간다.
  • 흰 방 만을 이용했을 때 목적지에 도달하지 못한다면, 검은방을 흰색으로 바꾼 경우를 이어서 진행하게 된다.

주의 할 점

  • 우선순위 큐는 기본적으로 max heap이다.
  • 오버로딩시에 역순으로 정렬할 수 있게 해야한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

struct spot {
    int cnt;
    int x, y;
};

struct cmp {
	bool operator()(const spot& a, const spot& b) {
        return a.cnt > b.cnt;
	}
};

priority_queue<spot, vector<spot>, cmp> pq;

char board[52][52];
bool visited[52][52];
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
int n;

int Dijstra() {
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        if (cur.x == n - 1 and cur.y == n - 1) return cur.cnt;

        for (int dir = 0; dir < 4; ++dir) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];

            if (nx < 0 or nx >= n or ny < 0 or ny >= n) continue;
            if (visited[nx][ny]) continue;

            visited[nx][ny] = true;

            if (board[nx][ny] == '1') pq.push({ cur.cnt, nx, ny });
            else  pq.push({ cur.cnt + 1, nx, ny });
        }
    }
    return -1;
}

void Solve() {
    visited[0][0] = true;
    pq.push({ 0,0,0 });
    cout << Dijstra() << "\n";
}

void Input() {
    cin >> n;

    string line;
    for (int i = 0; i < n; ++i) {
        cin >> line;
        for (int ii = 0; ii < n; ++ii) {
            board[i][ii] = line[ii];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • visit변수가 이미 사용되고 있는 저지들이 있다. (구름, leetcode) 앞으로는 visited로 하자.
  • 다른분들 풀이를 보니 deque를 이용해 BFS로 푸신분들도 있었다.
  • visited를 3차원으로 관리해야 하나 잠시 고민했었다. 애매할땐 시뮬레이션을 통해 설계를 검증하자.