[BOJ-2665]미로만들기

http://acmicpc.net/problem/2665

[풀이방법]

값을 갱신시키는 BFS

지도의 방문위치에 도달하기까지 최소로 색을 바꾸는 작업을 진행하면된다. 

즉, 시작위치부터 도착위치까지 도달한다. 

1. BFS를 진행한다.

2. 현재위치를 기준으로 다음위치를 본다.

2-1. 다음위치가 검은색방일 때, 값이 현재위치+1 값보다 크다면? 다음위치 = 현재위치+1 값을 갱신시키며, Q에 넣는다.

2-2. 다음위치가 흰색방일 때, 값이 현재위치보다 값이 크다면? 다음위치 = 현재위치 로 값을 갱신시키고, Q에 넣는다.

3. 위 BFS 과정이 끝나면 끝방의 vis 값을 출력해주면 된다.

[C++11]

#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
const int m = 55;
const int dr[] = { 0,0,1,-1 };
const int dc[] = { 1,-1,0,0 };
char im[m][m];
int imap[m][m];
int vis[m][m];
const int INF = 1 << 22;
 
struct pos {
    int r, c, m ;
    pos() {}
    pos(int ir, int ic, int im) : r(ir), c(ic), m(im) {}
};
 
int main() {
    int n;
    memset(imap, -1, sizeof(imap));
    scanf("%d", &n);
    for (int r = 0; r < n; r++) {
        scanf("%s", im[r]);
        for (int c = 0; c < n; c++) {
            imap[r][c] = im[r][c] - '0';
        }
    } // input
 
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            vis[r][c] = INF;
        }
    }
    vis[0][0] = 0;
    queue<pos> Q;
    Q.push(pos(0, 0, 0));
    while (!Q.empty()) {
        int hr = Q.front().r;
        int hc = Q.front().c;
        int hm = Q.front().m;
        Q.pop();
        //if()
 
        for (int i = 0; i < 4; i++) {
            int tr = hr + dr[i];
            int tc = hc + dc[i];
 
            if (tr < 0 || n <= tr || tc < 0 || n <= tc) continue;
 
            if (imap[tr][tc] == 0 && (vis[tr][tc] > (vis[hr][hc] + 1))) {
                vis[tr][tc] = vis[hr][hc] + 1;
                Q.push(pos(tr, tc, vis[tr][tc]));
            }
            else if (imap[tr][tc] == 1 && (vis[tr][tc] > vis[hr][hc])) {
                vis[tr][tc] = vis[hr][hc];
                Q.push(pos(tr, tc, vis[tr][tc]));
            }
        }
    }
 
    printf("%d\n", vis[n - 1][n - 1]);
 
    return 0;
}