[BOJ] 백준 23352번 방탈출 C++ (제1회 한국항공대학교 프로그래밍 경진대회 문제)

문제

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

23352번: 방탈출

풀이

BFS + 브루트포스로 해결할 수 있었다.

문제를 해결하기위해 최단거리를 구해야하므로 dist라는 2차원 배열을 만들어주었다 dist를 -1로 초기화 시켜준 이유는 따로 방문 처리 배열을 만들지 않고 dist의 값이 -1일때는 아직 방문을 하지 않은 좌표라는 것을 이용하기 위해서이다. 

최대 크기의 비밀번호를 구하기위해서는 모든 좌표(0이 아닌 곳)에 대해 탐색을 해야하며 탐색을 하며 현재 최단 거리를 갱신하였을때 시작 좌표의 원소 + 현재 좌표로 비밀번호에 대한 갱신을 해줄 수 있다. 

또한 최단 거리를 갱신하였을때도 두가지 분기로 나뉘는데 현재 최단 거리와 이번에 갱신한 거리가 같으면 현재 비밀번호의 최댓값과 이번에 생성된 비밀번호를 각각 구해 둘 중 최댓값으로 넘겨주고, 그게 아니라 이번에 갱신한 거리가 더 크면 문제에 조건에 따라 더 긴 경로의 비밀번호를 넘겨주어야 하므로 이번에 생성된 비밀번호가 현재 비밀번호의 최댓값으로 넘어가게 된다.

이러한 방법으로 모든 좌표에 대해 탐색을 하면 정답을 구할 수 있다.

코드

+#include<iostream>
#include<algorithm>
#include<queue>
#define x first
#define y second

using namespace std;

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0, 1, 0, -1 };
int n, m;
int board[51][51];
int globalMaxDist = -2;
int password = -2;

void input();
void bfs(int startX, int startY);

int main()
{

	cin.tie(0);
	ios::sync_with_stdio(0);

	input();

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] != 0)
			{
				bfs(i, j);
			}
		}
	}

	cout << password;
}

void input()
{
	cin >> n >> m;

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

void bfs(int startX, int startY)
{
	queue<pair<int, int>> q;

	int dist[51][51];
	int desX = 0;
	int desY = 0;

	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			dist[i][j] = -1;
		}
	}

	q.push({ startX, startY });
	dist[startX][startY] = 0;

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

		if (dist[cur.x][cur.y] >= globalMaxDist)
		{
			if (dist[cur.x][cur.y] > globalMaxDist)
			{
				password = board[startX][startY] + board[cur.x][cur.y];
			}
			else
			{
				password = max(board[startX][startY] + board[cur.x][cur.y], password);
			}
			globalMaxDist = dist[cur.x][cur.y];
		}

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

			if (nx < 0 || nx > n || ny < 0 || ny > m)
			{
				continue;
			}
			if (board[nx][ny] == 0 || dist[nx][ny] >= 0)
			{
				continue;
			}

			q.push({ nx, ny });
			dist[nx][ny] = dist[cur.x][cur.y] + 1;
		}
	}
}