#BOJ 4179 ๐Ÿ”ฅ๋ถˆ!

Wonder_Why (Today I learned)ยท2022๋…„ 1์›” 10์ผ
0

BOJ

๋ชฉ๋ก ๋ณด๊ธฐ
25/70

๐Ÿ”ฅ๋ถˆ!

BFS๋ฅผ 2๋ฒˆ ๋Œ๋ฆฌ๋Š” ๋ฌธ์ œ!๐Ÿ”ฅ

'ํƒˆ๋ชจ ๊ฑธ๋ฆด๋ป”ํ–ˆ๋‹ค.'

์‹œ๊ฐ„ ์ œํ•œ	๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ	์ œ์ถœ	์ •๋‹ต	๋งžํžŒ ์‚ฌ๋žŒ	์ •๋‹ต ๋น„์œจ
1 ์ดˆ	256 MB	17718	4275	2912	22.160%

๋ฌธ์ œ
์ง€ํ›ˆ์ด๋Š” ๋ฏธ๋กœ์—์„œ ์ผ์„ ํ•œ๋‹ค. ์ง€ํ›ˆ์ด๋ฅผ ๋ฏธ๋กœ์—์„œ ํƒˆ์ถœํ•˜๋„๋ก ๋„์™€์ฃผ์ž!

๋ฏธ๋กœ์—์„œ์˜ ์ง€ํ›ˆ์ด์˜ ์œ„์น˜์™€ ๋ถˆ์ด ๋ถ™์€ ์œ„์น˜๋ฅผ ๊ฐ์•ˆํ•ด์„œ ์ง€ํ›ˆ์ด๊ฐ€ ๋ถˆ์— ํƒ€๊ธฐ์ „์— ํƒˆ์ถœํ•  ์ˆ˜ ์žˆ๋Š”์ง€์˜ ์—ฌ๋ถ€, ๊ทธ๋ฆฌ๊ณ  ์–ผ๋งˆ๋‚˜ ๋นจ๋ฆฌ ํƒˆ์ถœํ•  ์ˆ˜ ์žˆ๋Š”์ง€๋ฅผ ๊ฒฐ์ •ํ•ด์•ผํ•œ๋‹ค.

์ง€ํ›ˆ์ด์™€ ๋ถˆ์€ ๋งค ๋ถ„๋งˆ๋‹ค ํ•œ์นธ์”ฉ ์ˆ˜ํ‰๋˜๋Š” ์ˆ˜์ง์œผ๋กœ(๋น„์Šค๋“ฌํ•˜๊ฒŒ ์ด๋™ํ•˜์ง€ ์•Š๋Š”๋‹ค) ์ด๋™ํ•œ๋‹ค.

๋ถˆ์€ ๊ฐ ์ง€์ ์—์„œ ๋„ค ๋ฐฉํ–ฅ์œผ๋กœ ํ™•์‚ฐ๋œ๋‹ค.

์ง€ํ›ˆ์ด๋Š” ๋ฏธ๋กœ์˜ ๊ฐ€์žฅ์ž๋ฆฌ์— ์ ‘ํ•œ ๊ณต๊ฐ„์—์„œ ํƒˆ์ถœํ•  ์ˆ˜ ์žˆ๋‹ค.

์ง€ํ›ˆ์ด์™€ ๋ถˆ์€ ๋ฒฝ์ด ์žˆ๋Š” ๊ณต๊ฐ„์€ ํ†ต๊ณผํ•˜์ง€ ๋ชปํ•œ๋‹ค.

์ž…๋ ฅ

์ž…๋ ฅ์˜ ์ฒซ์งธ ์ค„์—๋Š” ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋œ ๋‘ ์ •์ˆ˜ R๊ณผ C๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹จ, 1 โ‰ค R, C โ‰ค 1000 ์ด๋‹ค. R์€ ๋ฏธ๋กœ ํ–‰์˜ ๊ฐœ์ˆ˜, C๋Š” ์—ด์˜ ๊ฐœ์ˆ˜์ด๋‹ค.
๋‹ค์Œ ์ž…๋ ฅ์œผ๋กœ R์ค„๋™์•ˆ ๊ฐ๊ฐ์˜ ๋ฏธ๋กœ ํ–‰์ด ์ฃผ์–ด์ง„๋‹ค.
๊ฐ๊ฐ์˜ ๋ฌธ์ž๋“ค์€ ๋‹ค์Œ์„ ๋œปํ•œ๋‹ค.
#: ๋ฒฝ
.: ์ง€๋‚˜๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ณต๊ฐ„
J: ์ง€ํ›ˆ์ด์˜ ๋ฏธ๋กœ์—์„œ์˜ ์ดˆ๊ธฐ์œ„์น˜ (์ง€๋‚˜๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ณต๊ฐ„)
F: ๋ถˆ์ด ๋‚œ ๊ณต๊ฐ„
J๋Š” ์ž…๋ ฅ์—์„œ ํ•˜๋‚˜๋งŒ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

์ง€ํ›ˆ์ด๊ฐ€ ๋ถˆ์ด ๋„๋‹ฌํ•˜๊ธฐ ์ „์— ๋ฏธ๋กœ๋ฅผ ํƒˆ์ถœ ํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ IMPOSSIBLE ์„ ์ถœ๋ ฅํ•œ๋‹ค.
์ง€ํ›ˆ์ด๊ฐ€ ๋ฏธ๋กœ๋ฅผ ํƒˆ์ถœํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์—๋Š” ๊ฐ€์žฅ ๋น ๋ฅธ ํƒˆ์ถœ์‹œ๊ฐ„์„ ์ถœ๋ ฅํ•œ๋‹ค.

์˜ˆ์ œ ์ž…๋ ฅ 1

4 4
####
#JF#
#..#
#..#

์˜ˆ์ œ ์ถœ๋ ฅ 1

3

๊ตฌํ˜„

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int dist_fire[1001][1001];
int run[1001][1001];

string maze[1001];

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

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int r, c;
	cin >> r >> c;
	queue<pair<int, int>> Q_fire;
	queue<pair<int, int>> Q_run;
	for (int i = 0; i < r; i++)
	{
		cin >> maze[i];
	}

	for(int i = 0 ; i < r; i ++)
		for (int j = 0; j < c; j++)
		{
			dist_fire[i][j] = -1;
			run[i][j] = -1;
		}

	for (int i = 0; i < r; i++)
	{
		int j = 0;
		for (auto& e : maze[i])
		{
			if (e == 'F')
			{
				Q_fire.push({i,j});
				dist_fire[i][j] = 0;
			}
			j++;
		}
	}

	for (int i = 0; i < r; i++)
	{
		int j = 0;
		for (auto& e : maze[i])
		{
			if (e == 'J')
			{
				Q_run.push({ i,j });
				run[i][j] = 0;
			}
			j++;
		}
	}
	//1st bfs

	while (!Q_fire.empty())
	{
		auto cur = Q_fire.front(); Q_fire.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = cur.X + dx[i];
			int ny = cur.Y + dy[i];

			if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
			if (maze[nx][ny] == '#' || dist_fire[nx][ny] >= 0) continue;
			Q_fire.push({ nx,ny });
			dist_fire[nx][ny] = dist_fire[cur.X][cur.Y] + 1;
		}

	}
	//2st bfs
	while (!Q_run.empty())
	{
		auto cur = Q_run.front(); Q_run.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = cur.X + dx[i];
			int ny = cur.Y + dy[i];
			if (nx < 0 || nx >= r || ny < 0 || ny >= c)
			{
				cout << run[cur.X][cur.Y] + 1;
				return 0;
			}
			if (maze[nx][ny] == '#' || run[nx][ny] >= 0) continue;
			if (dist_fire[nx][ny] != -1 && dist_fire[nx][ny] <= run[cur.X][cur.Y] + 1) continue;
			Q_run.push({ nx,ny });
			run[nx][ny] = run[cur.X][cur.Y] + 1;
		}
	}
	cout << "IMPOSSIBLE";
	return 0;

}

  • ์ฝ”๋“œ๊ฐ€ ์ข€ ๋”๋Ÿฌ์šด ๋“ฏ ํ•˜๋‹ค.
  • ์ •๋ฆฌ ์ข€ ํ•ด์„œ ๋‹ค์‹œ ์˜ฌ๋ ค์•ผ๊ฒ ๋‹ค...
profile
์ „์ž๊ณผ ๋จธํ•™์ƒ

0๊ฐœ์˜ ๋Œ“๊ธ€