[백준/BOJ] 백준 16441번 : 아기돼지와 늑대

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

16441번: 아기돼지와 늑대

 

각 늑대의 위치에서 dfs(깊이 우선 탐색)을 진행하여, 늑대가 도달하지 못하는 초원을 파악했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int n, m;
vector<string> board;
vector<pair<int, int>> wolf;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int visited[105][105];

void dfs(pair<int, int> here) {

	visited[here.first][here.second] = 1;

	for (int dir = 0; dir < 4; dir++) {
		pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

		//there위치가 빙판일때
		if (board[there.first][there.second] == '+') {
			//초원을 밟거나 산에 부딪칠 때까지 이동
			while (1) {
				there = make_pair(there.first + dxdy[dir][0], there.second + dxdy[dir][1]);

				//초원에 도착했을때
				if (board[there.first][there.second] == '.') {
					break;
				}

				//산에 도착했을때
				if (board[there.first][there.second] == '#') {
					there = make_pair(there.first - dxdy[dir][0], there.second - dxdy[dir][1]);
					break;
				}
			}
		}

		//there위치가 산일때
		else if (board[there.first][there.second] == '#') {
			continue;
		}

		//there위치를 방문한적 없을때
		if (visited[there.first][there.second] == 0) {
			dfs(there);
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;

		board.push_back(input);

		for (int j = 0; j < m; j++) {
			if (input[j] == 'W') {
				wolf.push_back(make_pair(i, j));
			}
		}
	}

	for (int i = 0; i < wolf.size(); i++) {
		dfs(wolf[i]);
	}

	vector<string> result;
	result = board;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == '.' && visited[i][j] == 0) {
				result[i][j] = 'P';
			}
		}
	}

	for (int i = 0; i < n; i++) {
		cout << result[i] << "\n";
	}

	return 0;
}