2665 미로만들기

2665 미로만들기

BFS를 배우고 있거나 연습하는 사람에게 좋은 문제인거 같다.

1. pair형으로 두가지 정보를 저장할 d 배열을 만든다. first=뚫은 횟수, second=거리비용

2. 한번도 방문하지 않았거나 뚫은횟수가 더 적은경우 무조건 갱신

3. 이미 방문했고 벽을 뚫은 횟수가 같을경우 거리비용이 더 적은것으로 갱신

4. d[n][n]에 저장되어있는 벽을뚫은 최소 횟수 출력.

#include <iostream>
#include <queue>
#define P pair<int,int>
using namespace std;
 
struct Node{
    int x,y,cnt;
    Node(int x, int y, int c) :x(x), y(y), cnt(c){}
};
 
int map[51][51];
P d[51][51];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int n;
char buf[51];
 
void bfs() {
    queue<Node> q;
    q.push(Node(1, 1, 0));
    //P(0, 1) 0번뚫고 1번만에 도착
    d[1][1] = P(0, 1);
 
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int ax = x + dx[i];
            int ay = y + dy[i];
            if (ax > 0 && ay > 0 && ax <= n && ay <= n) {
                //길이 뚫려있는 경우
                if (map[ax][ay] == 1) {
                    //방문기록이 없거나 방을 더 적게 뚫은경우 무조건 갱신
                    if (d[ax][ay].second == 0 || d[ax][ay].first > cnt) {
                        d[ax][ay] = P(cnt, d[x][y].second + 1);
                        q.push(Node(ax, ay, cnt));
                    }
                    else {
                        //방문기록이 있고 뚫기를 동일하게 사용한경우
                        if (d[ax][ay].first == cnt) {
                            if (d[ax][ay].second > d[x][y].second + 1) {
                                d[ax][ay].second = d[x][y].second + 1;
                                q.push(Node(ax, ay, cnt));
                            }
                        }
                    }
                }
                //길이 막혀있는 경우
                else {
                    //처음 방문하거나 더 적게 뚫은경우
                    if (d[ax][ay].second == 0 || d[ax][ay].first > cnt + 1) {
                        d[ax][ay] = P(cnt + 1, d[x][y].second + 1);
                        q.push(Node(ax, ay, cnt + 1));
                    }
                    else {
                        //방문기록이 있고 뚫기를 동일하게 사용한경우
                        if (d[ax][ay].first == cnt + 1) {
                            if (d[ax][ay].second > d[x][y].second + 1) {
                                d[ax][ay].second = d[x][y].second + 1;
                                q.push(Node(ax, ay, cnt + 1));
                            }
                        }
                    }
                }
            }
        }
    }
 
    printf("%d\n", d[n][n].first);
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", &buf);
        for (int j = 1; j <= n; j++) {
            map[i][j] = buf[j - 1] - '0';
        }
    }
    bfs();
}