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

문제

윌리암슨수액빨이딱따구리 식구의 위치에서 가장 가까운 음식 사이의 최단 거리

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

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

조건

• 정보섬 2층
  • 0: 빈 복도 -> 지나갈 수 있음.
  • 1: 장애물 -> 지나갈 수 없음.
  • 2: 식구
  • 3: 청국장
  • 4: 스시
  • 5: 맥앤치즈
  • 2, 3, 4, 5는 지나갈 수 있다.
• 윌리암슨수액빨이딱따구리
  • 단위 시간마다 한 칸, 상하좌우로 이동 가능

 

입출력

입력

• 정보섬 2층의 크기 n과 m
• 정보섬은 0, 1, 2, 3, 4, 5로 구성

출력

• 음식을 먹을 수 있는 경우
  • 첫째 줄: TAK 출력
  • 둘째 줄: 현위치에서 가장 빨리 도착할 수 있는 음식까지의 최단 거리를 출력
• 음식을 먹을 수 없는 경우
  • NIE 출력

 

---

어떤 유형일까?

첫번째 시도. 특정 위치에서 음식까지의 최단 거리를 찾는 것이므로 dfs가 맞지 않을까?

 

문제에서 주어진 예제 입력 1을 통해 살펴보자.

2	0	0
0	0	3
0	4	5

정보섬의 크기와 같은 거리 배열을 두고 깊이 우선 탐색을 통해 거리를 1씩 증가시켜 나간다. 음식을 만날 때마다 현재 최단 거리 값과 비교하여 작으면 업데이트 해준다.

 

두번째 시도. dfs로 하니 시간초과가 발생하였다.

최단거리를 구해야 할 경우, BFS가 유리하다고 한다.

dfs로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 
bfs의 경우 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리이기 때문이다!

---

코드 구현

bfs 구현을 위하여 큐를 이용하였다.

시작점을 큐에 넣은 후 상하좌우를 탐색하며 

위치가 섬 내부이고 방문하지 않은 경우에 큐에 넣으며 탐색을 하였다. 

이 과정에서 음식의 위치가 도달한 경우

해당 음식 위치까지의 최단 거리와 현재 최단 거리를 비교하여 

해당 음식 위치까지의 최단 거리가 더 작은 경우 업데이트해주었다.

---

성공 코드(내 코드)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m, answer=2146000000;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1, 0};
vector<vector<int> > map(3001, vector<int>(3001, 0));
vector<vector<int> > dis(3001, vector<int>(3001, 2146000000));
vector<vector<int> > visited(3001, vector<int>(3001, 0));

struct Loc{
    int x, y;
    Loc(int x, int y){
        this->x=x;
        this->y=y;
    }
};

void bfs(int x, int y){
    queue<Loc> q;
    q.push(Loc(x, y));
    while(!q.empty()){
        Loc tmp=q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int nx=tmp.x+dx[i], ny=tmp.y+dy[i];
            if(nx>=0 && nx<n && ny>=0 && ny<m){
                if(map[nx][ny]!=1 && visited[nx][ny]==0){
                    dis[nx][ny]=dis[tmp.x][tmp.y]+1;
                    if(map[nx][ny]>=2){
                        if(dis[nx][ny]<answer){
                            answer=dis[nx][ny];
                        }
                    } else{
                        visited[nx][ny]=1;
                        q.push(Loc(nx, ny));
                    }
                }
            }
        }
    }
}

int main(){
    // freopen("input.txt", "rt", stdin);
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    int s, e;
    string num;
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> num;
        for(int j=0; j<m; j++){
            map[i][j]=num[j]-'0';
            if(map[i][j]==2){
                s=i;
                e=j;
                dis[s][e]=0;
            }
        }
    }
    visited[s][e]=1;
    bfs(s, e);
    if(answer!=2146000000){
        cout << "TAK\n";
        cout << answer;
    } else{
        cout << "NIE\n";
    }

    return 0;
}

---

후기

dfs를 사용하여 시간초과를 겪으며 bfs가 최단거리를 구할 시에 더 빠르다는 것을 알게되었다.