1. 문제
링크텍스트
윌리암슨수액빨이딱따구리 세 식구가 정보섬에 올라왔다!
세 윌리암슨수액빨이딱따구리는 정보섬 2층 어딘가에 모여 앉아 쉬고 있었는데, 저 멀리 청국장과 스시와 맥앤치즈가 있는 것을 발견했다! 아빠는 청국장, 엄마는 스시, 아이는 맥앤치즈가 먹고 싶다. 그래서 이 셋은 현위치로부터 가장 가까운 음식을 먹으러 가기로 했다.
정보섬 2층은 An×m의 격자로 표현된다. 어떤 Ai,j가 0이면 빈 복도여서 지나갈 수 있고, 1이면 장애물로 막혀 지나갈 수 없다. 윌리암슨수액빨이딱따구리 식구는 2, 청국장은 3, 스시는 4, 맥앤치즈는 5이다. 윌리암슨수액빨이딱따구리는 단위 시간마다 한 칸, 상하좌우로 움직일 수 있다. 2, 3, 4, 5는 장애물이 아니므로 지나갈 수 있다. 격자 밖으로는 나갈 수 없으며 시작점으로부터 시작점까지의 거리는 0이다. 시작점은 윌리암슨수액빨리딱따구리의 위치, 즉 2의 위치이다.
과연 윌리암슨수액빨이딱따구리 식구는 어떤 음식에 더 빨리 도착할 수 있을까?
2. 입력/출력
첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106)
이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다.
2, 3, 4, 5는 반드시 하나씩 존재하며 2, 3, 4, 5가 아닌 나머지는 0 또는 1이다.
첫째 줄에 "TAK"(폴란드어로 YES를 의미)을 출력하고, 둘째 줄에 현위치에서 가장 빨리 도착할 수 있는 음식까지의 최단 거리를 출력한다.
아무 음식도 먹을 수 없으면 "NIE"(폴란드어로 NO를 의미)를 출력한다. 이외의 출력은 하지 않는다.
TAK과 NIE를 출력할 때 따옴표는 출력하지 않으며 반드시 대문자로 출력한다.
3. 풀이
BFS를 이용해 최단경로를 구하는 문제이다.
시작위치에서 BFS를 이용해 각 노드까지의 최단 경로를 구해준다.
-> visit[][] 배열을 이용해 bfs 탐색을 한 번 할 때 마다 이전 visit[][]에 +1을 한 값이 거리가 된다.
4. 코드
#include <iostream>
#pragma warning (disable:4996)
#include <queue>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
int map[3001][3001];
int visit[3001][3001];
int dx[4] = {1,-1,0,0};
int dy[4] = { 0,0,1,-1 };
void bfs(int x, int y) {
queue<pair<int, int>> q;
pair<int, int> cur;
q.push(pair<int, int>(x, y));
visit[x][y] = 1;
while (!q.empty()) {
cur = q.front();
q.pop();
for (int i = 0; i < 4;i++) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (map[nx][ny] != 1 && visit[nx][ny] == 0) {
visit[nx][ny] = visit[cur.first][cur.second] + 1;
q.push(pair<int, int>(nx, ny));
}
}
}
}
}
int main()
{
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(0);
cin >> n >> m;
int startx=0, starty=0;
for (int i = 0; i < n; i++) {
string tmp;
cin >> tmp;
for (int j = 0; j < m; j++) {
map[i][j] = tmp[j] - '0';
if (map[i][j] == 2) {
startx = i;
starty = j;
}
}
}
bfs(startx, starty);
int minN = 100000;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 3 || map[i][j] == 4 || map[i][j] == 5) {
if (visit[i][j] == 0) continue;
minN = min(minN, visit[i][j]);
}
}
}
if (minN == 100000) {
cout << "NIE";
}
else {
cout << "TAK\n";
cout << minN-1;
}
}
