[BOJ] 백준 17129번 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 C++

문제

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

17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

풀이

BFS + 최단거리로 해결할 수 있었다.

거리를 저장할 배열인 dist와 정보섬의 값을 저장할 배열인 board를 만들어 board를 입력받았다. 이때 해당 정보섬 좌표의 값이 2이면 해당 좌표가 시작점이므로 startX, startY라는 변수에 담아주었다.

이후에는 dist의 배열을 정보섬의 크기만큼 -1로 초기화 시켜주었다. dist를 -1로 초기화 시켜준 이유는 탐색을 하면서 dist의 값은 수시로 바뀔 것이고, 이때 탐색을 통해 도달하지 못한 좌표의 dist의 값은 -1일 것이니까 방문 처리 또한 판별해줄 수 있기 때문이다.

이후에 탐색을 진행하면서 음식(3, 4, 5)에 도달했다면 우리는 음식까지의 최단 거리를 구해주어야 하기 때문에 음식 좌표의 거리들의 최솟값을 구해주어 최단 거리를 구할 수 있다.

하지만 음식까지 도달하지 못한다면 최솟값을 구할 때 사용했던 변수의 초깃값이 바뀌지 않을 테니 이를 이용하여 도달했는지, 안 했는지 판단 해 주면 정답을 구할 수 있다.

코드

#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <string>
#define x first
#define y second

using namespace std;

int n, m;
int startX, startY;
int resultDist = 9000001;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };
int board[3001][3001];
int dist[3001][3001];
queue<pair<int, int>> q;

void initialValueSet();
void bfs();
void printResult();

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	initialValueSet();
	bfs();
	printResult();
}

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

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

		if (board[cur.x][cur.y] == 3 || board[cur.x][cur.y] == 4 || board[cur.x][cur.y] == 5)
		{
			resultDist = min(resultDist, 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] == 1 || dist[nx][ny] != -1)
			{
				continue;
			}

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

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

	for (int i = 0; i < n; i++)
	{
		string line;
		cin >> line;
		for (int j = 0; j < m; j++)
		{
			board[i][j] = line[j] - '0';
			if (board[i][j] == 2)
			{
				startX = i;
				startY = j;
			}
		}
	}

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

void printResult()
{
	if (resultDist != 9000001)
	{
		cout << "TAK" << "\n" << resultDist;
	}
	else
	{
		cout << "NIE";
	}
}