17) 백준 2665 - 미로만들기

2665번: 미로만들기 (acmicpc.net)

2665번: 미로만들기

---

#include <bits/stdc++.h>

using namespace std;

int N;
int x_p[4] = {0, 0, 1, -1};
int y_p[4] = {1, -1, 0, 0};
int room[50][50] = {0, };
int check[50][50] = {0, };

void bfs() {
	queue<pair<int, int> > q;
	int x, y;
	q.push(make_pair(0, 0));
	check[0][0] = 0;
	
	while(!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++) {
			int xp = x + x_p[i];
			int yp = y + y_p[i];
			if(xp < N && xp >= 0 && yp < N && yp >= 0 ) {
				if(room[xp][yp] == 1) {
					if(check[xp][yp] > check[x][y]) {
						check[xp][yp] = check[x][y];
						q.push(make_pair(xp, yp));
					}
				}
				else {
					if(check[xp][yp] > check[x][y] + 1) {
						check[xp][yp] = check[x][y]+1;
						q.push(make_pair(xp, yp));
					}
				}
			}
		}
	}
}

int main(void) {
	cin >> N;
	char c;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			cin >> c;
			room[i][j] = c - '0';
			check[i][j] = 99999999;
		}
	}
	
	bfs();
	
	cout << check[N-1][N-1];
}

처음에는 문의 색을 바꾸고 bfs 돌리자! 라고 생각했는데 막막했다.

 

다른 방법을 생각했는데 차라리 그냥 검은 방을 들어가고 검은 방의 갯수를 세는 방법으로 바꾸었다.

check에는 검은 방을 들어간 최소 갯수를 저장해두고 목적지에 도달하면 목적지의 check값을 출력해주었다.

 

음.. 쉬운듯 어려운듯 쉬운듯 ..음