백준14497 주난의 난(難)

작성일 | In

문제 링크

  • http://icpc.me/14497

문제 출처

  • 2017 선린 봄맞이 대회 K번

사용 알고리즘

  • BFS(Flood Fill)

시간복잡도

  • O(nm(n + m))

풀이

상하좌우 4방향으로 퍼지고, 최소 횟수를 물어보는 점에서 가장 먼저 BFS를 떠올릴 수 있습니다.

BFS를 한 번 돌릴 때 O(nm)이 걸립니다.
최악의 경우에도 (n + m)번 탐색을 하기 때문에 TLE가 나지 않습니다.

4방향으로 BFS를 돌려주시면 답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

int n, m;
int trash;
char arr[350][350];
char tmp[350][350];
char chk[350][350];
p a, b;
int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, 1, -1};

bool bfs(){
	queue<p> q;
	q.push(a);
	while(!q.empty()){
		p poped = q.front(); q.pop();
		for(int k=0; k<4; k++){
			int i = poped.x+di[k], j = poped.y+dj[k];
			if(1<=i && i<=n && 1<=j && j<=m && !chk[i][j]){
				chk[i][j] = 1;
				if(arr[i][j] == '#') return true;
				if(arr[i][j] == '1'){
					tmp[i][j] = '0'; continue;
				}
				q.push({i, j});
			}
		}
	}
	return false;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m; cin >> trash >> trash >> trash >> trash;
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
		cin >> arr[i][j];
		if(arr[i][j] == '*') a = {i, j};
		if(arr[i][j] == '#') b = {i, j};
	}

	int ans = 0;
	while(1){
		ans++;
		memset(chk, 0, sizeof(chk));
		memcpy(tmp, arr, sizeof(tmp));
		if(bfs()) break;
		memcpy(arr, tmp, sizeof(tmp));
	}
	cout << ans;
}