[백준 14997] 주난의 난

문제 링크 : https://www.acmicpc.net/problem/14497

14497번: 주난의 난(難)

주난이가 점프를 할 때마다

 

주난이를 둘러싸고 있는 친구들의 벽이 사라진다

 

즉, 주난이가 한번 점프를 하면

 

자신부터 탐색을 시작해서

 

탐색 경계를 제한하는 친구들이 사라지는 것이다

 

구현 방법은 bfs든 dfs든 상관없다.

 

중요한 것은 주난이부터 탐색을 시작해서

 

친구를 만나면 그 친구는 이번 점프로 제거된다는 것이다.

 

또한 친구가 제거되었으면 거기서는 탐색을 중지하고 돌아와야 된다

 

(그 뒤로는 점프의 영향이 닿지 않음으로)

---

#include <iostream>
#define n_ 300+5
using namespace std;

int n, m;
int fx, fy, tx, ty;
char arr[n_][n_];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

int is_found;
int chk[n_][n_];

void dfs(int x, int y, int i) {
	chk[x][y] = i;	//이미 방문했으므로 

	// 도둑을 발견하면
	if (arr[x][y] == '#') {
		cout << i << endl;	// 몇번째 점프인지 출력하고
		is_found = 1;	// main에서 루프탈출을 위해 찾은 사실 저장
		return;
	}

	if (arr[x][y] == '1') {		// 친구를 만났으면
		arr[x][y] = '0';	// 그 친구는 이번 파동으로 제거됨
		return;
	}

	// 상하좌우 네방향으로 탐색 후 이동
	for (int d = 0; d < 4; d++) {
		int nx = x + dx[d];
		int ny = y + dy[d];
		if (nx == 0 || ny == 0 || nx == n + 1 || ny == m + 1)continue;
		if (chk[nx][ny] == i)continue;	// 이미 방문했으면 갈 필요가 없음

		dfs(nx, ny, i);
	}
}

int main(void) {
	cin >> n >> m;
	cin >> fx >> fy >> tx >> ty;
	for (int i = 1; i <= n; i++) {
		scanf("%s", arr[i] + 1);
	}

	arr[fx][fy] = '0';	// 주난이는 빈칸으로 취급
	for (int i = 1;; i++) {	
		dfs(fx, fy, i);	// 주난이부터 시작하는 i번째 점프
		if (is_found) { return 0; }	// 도둑을 찾으면 루프는 종료
	}
}