2024 - 08- 29 C++ 코딩테스트 10주완성 D+34

백준 4179 문제 - 불!

 

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

 

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

 

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

 

불은 각 지점에서 네 방향으로 확산된다.

 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다.
(단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.)

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

#: 벽
.: 지나갈 수 있는 공간
J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
F: 불이 난 공간
J는 입력에서 하나만 주어진다.

 

출력

 

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

 

실습코드

 

#include <bits/stdc++.h>

using namespace std;

//1.변수 목록
//입력받을 미로 char 2차원 배열 a
//방문한 미로의 위치를 표기할 정수형 2차원 배열 visited
//불이 번진 곳을 표기하기 위한 char형 2차원 배열 fire
//미로의 행과 열을 입력받을 정수형 변수 n,m
//탐색을 하기 위한 방향 정수형 배열 dy[],dx[]
//J의 시작지점과 F의 시작지점을 집어넣을 pair int형 Vector StarPos
const int max_length = 1004;
char a[max_length][max_length],fire[max_length][max_length];
int visited[max_length][max_length];
int n, m;
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> startpos;
vector<int> ret;

//2-3-1-1-1 int dfs(int y,int x)
	//2-3-1-1-1. visited[y][x] = 1 로 값대입	
	//2-3-1-1-2. 0부터 3까지 반복문
	//2-3-1-1-2-1. int ny = y + dy[i]
	//2-3-1-1-2-2. int nx = x + dx[i]
	//2-3-1-1-2-3. 만약 ny < 0 || ny >= n || nx < 0 || nx >= m 이면 return visited[y][x];
	//2-3-1-1-2-4. 만약 a[ny][nx] == '.' && !visited[ny][nx] 이면 dfs(ny,nx) 과 visited[ny][nx] = visited[y][x]  	
void dfs(int y, int x)
{	
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= n || nx < 0 || nx >= m)
		{
			ret.push_back(visited[y][x]);
			memset(visited, 0, n * m);
		}
		if (a[ny][nx] == '.' && !visited[ny][nx] && !fire[ny][nx])
		{
			visited[ny][nx] = visited[y][x] + 1;
			dfs(ny, nx);			
		}
	}

	for (int j = 0; j < 4; j++)
	{
		int ny = startpos[1].first + dy[j];
		int nx = startpos[1].second + dx[j];

		startpos[1].first = ny;
		startpos[1].second = nx;

		fire[ny][nx] = 'F';
	}	
}

int main()
{
	//2.알고리즘
	//2-1. 행과열을 입력
	//2-2. 행과열만큼 반복문
	//2-2-1. 행렬의 값을 입력
	//2-2-2. 만약 행렬의 값이 'J' 면 J 위치 저장
	//2-2-3. 만약 행렬의 값이 'F' 면 F 위치 저장
	cin >> n >> m;

	startpos.push_back({ 0,0 });
	startpos.push_back({ 0,0 });

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];

			if (a[i][j] == 'J')
			{
				startpos[0].first = i;
				startpos[0].second = j;
			}
			else if (a[i][j] == 'F')
			{
				startpos[1].first = i;
				startpos[1].second = j;
			}
		}
	}

	
	//2-2. 행과열만큼 반복문 종료
	int cnt = n * m;

	dfs(startpos[0].first, startpos[0].second);
	//2-3-1-1. dfs(i,j)
	
	for (int i : ret)
	{
		if (i < cnt)
			cnt = i;
	}

	if (cnt == 0)
		cout << "IMPOSSIBLE";

	else
		cout << cnt;

	return 0;
}

 

예제를 넣어서 출력해보니 제대로 되어서 백준에 제출해보니..

 

 

흐규ㅠㅠ.. 

 

시간복잡도때문인지 시간초과가 뜬다.. 이유를 모르겠어서 실습코드랑 비교해보자

 

강의실습코드

 

#include <bits/stdc++.h> 
using namespace std;
const int INF = 987654321;
char a[1004][1004];
int n,m,sx,sy,dx[4]={-1,0,1,0},dy[4]={0,-1,0,1}, ret, y, x;
int fire_check[1004][1004], person_check[1004][1004];
bool in(int a,int b){
	return 0 <= a && a < n && 0 <= b && b < m;
}
int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0); 
	queue<pair<int, int>> q;
    cin >> n >> m;  
	fill(&fire_check[0][0], &fire_check[0][0] + 1004 * 1004, INF);
    for(int i = 0; i < n; i++){ 
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
            if(a[i][j] == 'F'){
                fire_check[i][j] = 1; q.push({i, j});
            }else if(a[i][j] == 'J'){
                sy = i; sx = j;
            }
        }
    } 

	while(q.size()){
        tie(y, x) = q.front(); 
		q.pop();
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(!in(ny,nx)) continue;
			if(fire_check[ny][nx] != INF || a[ny][nx]=='#') continue;
			fire_check[ny][nx] = fire_check[y][x] + 1;
			q.push({ny, nx});
		}
	}

	person_check[sy][sx]=1;
	q.push({sy,sx});
	while(q.size()){
		int y = q.front().first;
		int x = q.front().second;
		q.pop(); 
		if(x == m - 1 || y == n - 1 || x == 0 || y == 0){
            ret = person_check[y][x];
            break;
		}
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(!in(ny,nx)) continue;
			if(person_check[ny][nx] || a[ny][nx]=='#') continue; 
			if(fire_check[ny][nx] <= person_check[y][x] + 1) continue;
            person_check[ny][nx] = person_check[y][x] + 1;
            q.push({ny, nx});
		}
	} 
    if(ret != 0) cout << ret << "\n";
	else cout << "IMPOSSIBLE \n";
	return 0;
}
/*
3 3
...
.J.
... 
*/

 

Stack을 이용한 알고리즘과 불의 이동거리와 사람의 이동거리를 비교하는 코드가 핵심이다.

 

먼저 불의 이동거리를 Stack을 이용하여 이동할때 좌표가 ny,nx 이동하기전 좌표가 y,x 라고 하면,

 

fire_check[ny][nx] = fire_check[y][x] + 1 으로 이동거리를 구해준다.

 

그리고 사람 이동거리를 구하는데,

 

이때 사람의 이동거리가 불의 이동거리보다 같거나 크면 이미 거기는 불이 번져있는 것이므로 Continue 로 하여 패스해준다.

 

마지막으로 스택안에 좌표값이 행렬의 범위를 벗어나면 탈출이므로 해당좌표의 값을 출력해주면 된다!

 

스택을 이용한 문제가 항상 헷갈렸는데 오늘에서야 완벽히 이해가 가능한거 같다...!!