백준 17836번 공주님을 구해라!

🔒[문제 url]

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

🔑알고리즘

최단경로를 구하므로 BFS를 이용한다.
이동하는 경우는 다음과같다.
1. 그람이 없고 빈 공간으로 이동하는 경우
2. 그람이 있고 빈 공간으로 이동하는 경우
3. 그람이 있고 벽을 부수고 이동하는 경우

• 따라서, visited[2][101][101]을 선언하여 [0][i][j]에는 그람을 지닌 상태에서 $(i,j)$까지의 길이를, [1][i][j] 그람이 없는 상태에서 $(i,j)$까지의 길이를 기록한다.
  즉, 그람을 줍는 순간 visited[1][i][j] = visited[0][i][j]으로 갱신해줘야 한다.

🐾부분 코드

struct Soldier
{
	int x;
	int y;
	bool gram;
};

<용사 구조체>
BFS 탐색 시 용사의 좌표와 그람 보유 여부를 표시할 구조체를 선언한다.

bool inRange(int x,int y)
{
	return 0<x&&x<=n&&0<y&&y<=m;
}

<범위 체크 함수>
다음 탐색할 지점이 범위를 벗어난다면 false를 반환한다.

🪄전체 코드

#include <iostream>
#include <memory.h>
#include <queue>
#include <vector>
using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n,m,t;
int map[101][101];

typedef pair<int,int> pii;
int visited [2][101][101];
pii dir[4] = {{-1,0},{1,0},{0,-1},{0,1}};


void INPUT()
{
	IAMFAST
	cin >> n >> m >> t;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> map[i][j];
}

bool inRange(int x,int y)
{
	return 0<x&&x<=n&&0<y&&y<=m;
}

int BFS()
{
	struct Soldier
	{
		int x;
		int y;
		bool gram;
	};
	queue<Soldier> q;
	q.push({1,1,false});
	visited[false][1][1] = 1;

	while(!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		bool gram = q.front().gram;
		q.pop();

		//그람 획득
		if(map[x][y] == 2)
		{
			gram = true;
			visited[true][x][y] = visited[false][x][y];
		}
		//공주 구출
		if(x == n && y == m) return visited[gram][x][y];

		for(int i = 0; i < 4; i++)
		{
			int nx = x + dir[i].first;
			int ny = y + dir[i].second;

			if(!inRange(nx,ny)) continue;
			if(!gram && map[nx][ny] == 1) continue;

            //벽을 부수고 이동
			if(gram && !visited[true][nx][ny])
				q.push({nx,ny,true}),
				visited[true][nx][ny] = visited[true][x][y] + 1;
            //그람이 있으나 빈 공간으로 이동
			if(gram && !visited[false][nx][ny])
				q.push({nx,ny,true}),
				visited[false][nx][ny] = visited[true][x][y] + 1;
            //그람이 없고 빈 공간으로 이동
			else if(!gram && !visited[false][nx][ny])
				q.push({nx,ny,false}),
				visited[false][nx][ny] = visited[false][x][y] + 1;
		}
	}
	return 2e9;
}


void SOLVE()
{
	int time = BFS()-1;
	if(time <= t) cout << time;
	else cout <<"Fail";
}

int main()
{
	INPUT();
	SOLVE();
}

🥇문제 후기

기본 BFS에서 한 단계 업그레이드 된 꽤 흔한 유형의 문제이다.
상위 호환 문제로는 말이 되고픈 원숭이가 있으니 연습해보고싶다면 시도해보자.