[백준][bfs] 14497 주난의 난 c++ 구현

목차

https://www.acmicpc.net/problem/14497

문제

 

문제 구현 방향

bfs와 dfs를 활용하면 풀 수 있는 문제였다.

bfs를 통해 경로를 계산해주고 dfs를 통해 퍼져나가는 파동을 구현해주면 된다.

 

 

코드 구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;


int dx[4] = {0, 0, 1, -1};
int dy[4] = { 1, -1, 0, 0 };
int N, M, startX, startY, endX, endY;
char board[300][300] = { 0 };
int visit[300][300] = { 0 };
queue<pair<int, int>> q;

//파동이 퍼지는 것을 위한 dfs
void dfs(int x, int y,  int a) {

	visit[y][x] = a;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx <0 || nx > M || ny <0 || ny  > N)
			continue;
		if (!visit[ny][nx] && board[ny][nx] == '0') {
			dfs(nx, ny, a);   //0이 나오면 다시 탐색
		}
		else if (!visit[ny][nx] && (board[ny][nx] == '1'|| board[ny][nx] == '#')) {
			board[ny][nx] = '0';
			visit[ny][nx] = a;
			q.push({ nx, ny });  
			//여기서 return 넣어주면 안된다 -> 1이 나오더라 마저 탐색을 진행해야 한다.
		}
	}
}

void bfs() {
	q.push({ startX-1, startY-1 });
	visit[startY-1][startX-1] = 1;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx <0 || nx > M  || ny <0 || ny  > N)
				continue;
			if (!visit[ny][nx] && board[ny][nx] == '1') {
				q.push({ nx, ny });
				visit[ny][nx] = visit[y][x] + 1;  //최단 경로 계산하기 위함
				board[ny][nx] = '0';
			}
			//0이 나오면 dfs탐색을 시작한다.
			else if (!visit[ny][nx] && board[ny][nx] == '0') {
				dfs(nx, ny, visit[y][x] + 1);
				if (visit[endY-1][endX-1])
					return;
			}
			else if (!visit[ny][nx] && board[ny][nx] == '#') {
				visit[ny][nx] = visit[y][x] + 1; 
				return;
			}
		}
	}

}


int main() {
	char symbol;
	cin >> N >> M;
	cin >> startY >> startX >> endY >> endX;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> symbol;
			board[i][j] = symbol;
		}
	}
	bfs();
	
	cout << visit[endY - 1][endX - 1]-1;
}