SWEA 10966번 물놀이를 가자 C++ BFS, Flood Fill, 너비 우선 탐색

리뷰

 

땅에서 어떠한 물로 이동한다고 생각하면 굉장히 어렵게 느껴지나, 물에서 땅으로 퍼지는 시간을 구하면 쉽게 생각할 수 있는 문제

 

 

SW Expert Academy

 

문제 풀이

1. init 함수를 통해 정답을 출력할 변수 ans를 0으로 초기화 하고, 방문 배열을 전부 -1로 초기화 해준다.
2. input 함수를 통해 n과 m값을 받고 맵 정보를 받아온다, 이때 W의 좌표를 Pos 구조체 타입의 큐 q에 추가해 주고 해당 좌표의 방문 처리를 0으로 초기화 해준다.
3. 큐에 담긴 좌표를 통해 bfs 함수를 실행해 준다, 해당 좌표에서 퍼져나갈 수 있는 위치까지 쭉 퍼져나가면 된다.
4. 퍼져나가면서 방문 처리는 현재 좌표 + 1로 설정해 주고 ans에 다음 위치의 방문 값을 더해준다.
5. 모든 테스트 케이스에 대해 위 작업을 반복하고 각 테스트 케이스 마다 ans값을 출력해 주면 된다.

 

참고 사항

범위를 벗어나지 않으며, 다음 좌표의 방문 값이 -1이고 맵 상에서 L인 경우에만 이동 처리해주면 된다.

 

정답 코드

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;
int tc, n, m, ans;
string lst[1000];
int v[1000][1000];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

struct Pos {
	int x, y;
};
queue<Pos> q;

void init() {
	ans = 0;
	memset(v, -1, sizeof(v));
}

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> lst[i];
		for (int j = 0; j < m; j++) {
			if (lst[i][j] == 'W') {
				q.push({ i, j });
				v[i][j] = 0;
			}
		}
	}
}

void bfs() {
	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && v[nx][ny] == -1 && lst[nx][ny] == 'L') {
				v[nx][ny] = v[cx][cy] + 1;
				q.push({ nx, ny });
				ans += v[nx][ny];
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> tc;
	for (int c = 1; c <= tc; c++) {
		init();
		input();
		bfs();
		cout << "#" << c << " " << ans << "\n";
	}	
}