[백준 3055번 / C++] 탈출

bfs 문제이다. 

 

#접근방법 

 

1. 고슴도치, 물, 비버의 굴 위치를 저장 후 bfs() 호출 (물과 고슴도치의 위치를 각각 queue에 push)

2. 먼저 물의 위치가 저장된 queue에서 물의 좌표값을 pop 하면서 물이 이동할 수 있는 인접한 구역에 물로 바꾼다. 

3. 고슴도치의 위치에서 상하좌우로 갈수 있는 경우 dis라는 배열에 더해나간다. 

4. 고슴도치가 더이상 갈 수 있는 길이 없을 때 또는 고슴도치가 비버의 굴 위치에 도달했을 때 리턴 해준다. 

#include <iostream>
#include <tuple>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std; 
int m, n, a_y, a_x;
queue<pair<int, int>> w; //물이 차있는 곳
queue<pair<int, int>> q; //고슴도치가 이동할 수 있는 곳 
vector <string> map;
int dis[50][50]; 
int visited_w[50][50]; 
int visited_q[50][50]; 
int dx[4] = { 0,0,-1,1 }; 
int dy[4] = { 1,-1,0,0 }; 
int result = 0; 
void bfs() {
	int w_size = w.size(); 
	int q_size = q.size(); 
	int y, x; 
	if (q_size == 0)return; 
	while (w_size--) {
		tie(y, x) = w.front(); 
		w.pop(); 
		for (int i = 0; i < 4; i++) {
			int nx = dx[i] + x; 
			int ny = dy[i] + y; 
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue; 
			if (map[ny][nx] == 'D' ||map[ny][nx]=='X'|| visited_w[ny][nx])continue; 
			visited_w[ny][nx] = 1; 
			map[ny][nx] = '*'; 
			w.push({ ny,nx }); 
		}
	}
	while (q_size--) {
		tie(y, x) = q.front(); 
		if (y == a_y && x == a_x) {
			result = dis[y][x];
			return; 
		}
		q.pop(); 
		for (int i = 0; i < 4; i++) {
			int nx = dx[i] + x; 
			int ny = dy[i] + y; 
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue; 
			if (map[ny][nx] == 'X' || visited_q[ny][nx]||map[ny][nx]=='*')continue; 
			visited_q[ny][nx] = 1; 
			dis[ny][nx] = dis[y][x] + 1; 
			q.push({ ny,nx }); 
		}
	}
	bfs(); 
}
int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0); cout.tie(0); 
	cin >> m >> n; 
	for (int i = 0; i < m; i++) {
		string s; cin >> s;
		for (int j = 0; j < s.size(); j++) {
			if (s[j] == '.')continue; 
			else if (s[j] == 'D') { a_y = i; a_x = j; }
			else if (s[j] == '*') { 
				w.push({ i,j }); 
				visited_w[i][j] = 1; 
			}
			else if (s[j] == 'S') { 
				q.push({ i,j }); 
				visited_q[i][j] = 1; 			
			}
		}
		map.push_back(s); 
	}
	bfs(); 
	/*for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cout << dis[i][j] << " ";
		}cout << endl;
	}cout << endl; */
	if (!dis[a_y][a_x])cout << "KAKTUS"; 
	else cout << dis[a_y][a_x];	
	return 0; 
}

3055번: 탈출