C++ / 3055 / 탈출 ( 너비 우선 탐색 )

728x90

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

문제 요약

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 합니다. 이 숲에는 고슴도치가 한 마리 살고 있습니다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 합니다.

티떱숲의 지도는 R행 C열로 이루어져 있습니다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있습니다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있습니다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있습니다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장합니다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 됩니다. 물과 고슴도치는 돌을 통과할 수 없습니다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없습니다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성해야합니다.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없습니다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없습니다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문입니다.

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력합니다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력합니다.

문제 풀이

이전에 풀어보았던 불!과 거의 비슷한 맥락입니다.

문제의 핵심은 물이 지나간 노드의 가중치보다 고슴도치가 지나갈 가중치가 더 작으면 지나갈수 있다 입니다.

따라서 물 bfs와 고슴도치 bfs두번 ( 물이 많으면 2번 이상이지만 ) 을 돌리는게 중요합니다.

1. 맵을 입력받습니다 맵을 받으면서 고슴도치 위치, 물 위치, 비버 동굴 위치를 따로 저장합니다. 물은 배열로 저장하였습니다.

2. 물 먼저 bfs 탐색을 해줍니다. 가중치를 저장해둘 dist 배열을 1e9로 초기화 해두고 탐색합니다.

3. 방문체크는 따로 하지 않습니다. 그저 현재 탐색하려는 노드가 1e9가 아니면 방문한것이기 때문에 스킵합니다.

3. 물 bfs 탐색을 마치면 고슴도치 탐색을 해줍니다. 위에 써있는데로 현재 dist배열이 고슴도치의 가중치보다 값이 작으면 스킵 합니다. ( 물이 더 빨리 지나가는 경우임 )

4. 고슴도치의 가중치가 더 작으면 탐색을 이어갑니다.

5. 탐색을 마치면 비버 동굴의 위치의 가중치가 1e9 이면 ( 물이 막아서 고슴도치 bfs가 탐색 못함 ) " KAKTUS " 를 출력하고 아닐 경우 가중치를 출력합니다.

주의할 점

본인 코드에서 물 bfs 탐색 할때에

			if (dist[ny][nx] <= dist[y][x] + 1)
			{
				continue;
			}

이렇게 썼다가 메모리 초과가 났습니다.

방문 체크 미흡

코드

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

using namespace  std;

int dy[4] = { 0, 1,  0, -1 };
int dx[4] = { 1, 0, -1, 0 };


int r, c, hy, hx, by, bx;
vector<vector<char>>v;
// 물 위치 담을 배열
vector<pair<int, int>>w;
int dist[54][54];

void print2()
{
	puts("");
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cout << dist[i][j];
		}
		puts("");
	}
	puts("");
}


void bfs(int y, int x)
{
	queue<pair<int, int>>q;
	q.push({ y, x });
	dist[y][x] = 0;

	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny >= r || ny < 0 || nx >= c || nx < 0)
			{
				continue;
			}
			// 비버 동굴 까지 체크
			if (v[ny][nx] != '.' && v[ny][nx] != 'D')
			{
				continue;
			}
			// 물이 더 빨리 도착한곳은 탐색 안함
			if (dist[ny][nx] <= dist[y][x] + 1)
			{
				continue;
			}
			dist[ny][nx] = dist[y][x] + 1;
			q.push({ ny, nx });
		}
	}
}

// 물 bfs 
void bfsW(int y, int x)
{
	queue<pair<int, int>>q;
	q.push({ y, x });
	dist[y][x] = 0;

	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny >= r || ny < 0 || nx >= c || nx < 0)
			{
				continue;
			}
			if (v[ny][nx] != '.')
			{
				continue;
			}
			if (dist[ny][nx] != 1e9)
			{
				continue;
			}
			dist[ny][nx] = dist[y][x] + 1;
			q.push({ ny,nx });
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> r>> c;
	v.resize(r, vector<char>(c));
	fill(&dist[0][0], &dist[r][c], 1e9);
	for (int i = 0; i < r; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < c; j++)
		{
			v[i][j] = s[j];
			// 고슴도치 위치
			if (v[i][j] == 'S')
			{
				hy = i;
				hx = j;
			}
			// 물 위치
			if (v[i][j] == '*')
			{
				w.push_back({ i, j });
			}
			// 비버 동굴 위치
			if (v[i][j] == 'D')
			{
				by = i;
				bx = j;
			}
		}
	}

	// 물 퍼지게 
	for (int i = 0; i < w.size(); i++)
	{
		bfsW(w[i].first, w[i].second);
	}
	//print2();
	// 고슴도치 탐색
	bfs(hy, hx);
	//print2();
	// 
	// 비버 동굴에 도달하지 못한 경우
	if (dist[by][bx] == 1e9)
	{
		cout << "KAKTUS";
	}
	else
	{
		cout << dist[by][bx];
	}
	return 0;
}

예제 1

3 3
D.*
...
.S.

결과 1

예제 2

3 3
D.*
...
..S

결과 2

예제 3

3 6
D...*.
.X.X..
....S.

결과 3

예제 4

5 4
.D.*
....
..X.
S.*.
....

결과 4