[BFS] 5213번 과외맨

5213번 과외맨

 

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

 

문제

과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다.

얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 동안 과외 노트를 훔쳐갔다. 과외맨은 빼앗긴 노트를 찾아오기 위해 인천 공항으로 가서 과테말라로 가는 비행기를 탔다.

일단 언어가 통하지 않기 때문에, 과외맨은 자신의 특기를 살려서 일주일간 과테말라에서 스페인어를 과외 받았다.

오랜 고서에 의하면, 고대 마야인은 하늘을 날아다니는 재주가 있었다고 한다. 과외맨은 매일 밤 하늘을 바라보며 마야인들의 흔적을 찾으려고 애를 썼다.

그렇게 한 달이 지났을까... 한국에선 이민혁 실종 사건이 연일 대서특필 되고 있고, 사람들은 사라진 과외맨을 찾으며 시청 광장에서 촛불 집회를 했다. 과외맨도 이런 사실에 안타까움을 느꼈다. 하지만, 과외 노트 없는 과외맨은 평범한 대학생과 같기 때문에 아직 돌아갈 수 없었다.

과외 노트의 단서는 뜻하지 않게 스페인어 과외를 받던 중에 알게 되었다. 과외맨의 과외 선생님이 주말을 이용해서 등산을 하던 사이에 고대 마야의 사원으로 보이는 것을 발견했고, 민혁이에게 과외 노트가 거기에 있는 것 같다고 알려주었다.

과외맨은 즉시 과외 노트를 찾으러 고대 마야의 사원으로 여행을 떠났다.

고대 마야의 사원의 입구로 들어간 과외맨은 매우 놀랐다. 바로 과외 노트가 자신의 눈 앞에 있는 것 이었다. 과외맨은 이적의 다행이다를 부르면서 과외 노트를 집으려고 했지만, 그것은 노트의 홀로그램이었다. 이어서 고대 마야인의 목소리가 사원을 가득 채우기 시작했다. 하지만, 고대 마야인은 스페인어를 사용하지 않았다. 과외맨은 닥터후에게 전화를 걸어서 자신에게 타디스의 번역 프로토콜을 제공해 줄 수 있는지를 물어 보았다. 닥터는 흔쾌히 요청을 받아들였고, 민혁이는 마야인의 메시지를 듣기 위해 밖으로 나갔다가 다시 들어왔다.

"하하하. 과외 노트를 돌려 받고 싶나? 그럼 여기로 와서 가져가 보시지. 하하하하"

과외맨의 과외 노트는 입구의 반대편에 있고, 그 사이에는 절벽이 있었다. 갑자기 하늘에서 거대한 도미노 타일이 떨어졌고, 그 사이를 연결하는 다리를 만들었다.

도미노 타일은 두 조각으로 나누어져 있었고, 각 조각은 정사각형이다. 조각에는 1과 6사이의 숫자가 써져 있다.

타일은 N줄로 놓여져 있고, 홀수 줄에는 N개의 타일이, 짝수 줄에는 N-1개의 타일이 놓여져 있다. 아래 그림은 (N=5)일 때 타일이 놓여져 있는 형태이다.

한 타일에서 다른 타일로 넘어가려면, 두 타일이 인접해야 한다. 또, 같은 변을 공유하는 조각에 쓰여 있는 숫자가 같아야 한다.

과외맨은 반대편으로 넘어가기 위해서 첫 줄의 가장 첫 타일에서 마지막 줄의 가장 마지막 타일로 이동하는 가장 짧은 경로를 찾으려고 한다.

타일은 row-major order에 의해서 번호가 매겨져 있으며, 첫 번째 줄의 첫 타일의 번호는 1, 마지막 타일의 번호는 N이다. 두 번째 줄에서 첫 타일의 번호는 N+1이고, 마지막 타일의 번호는 2*N-1이다.

첫 줄의 첫 타일로만 과외맨이 들어갈 수 있고, 마지막 줄의 마지막 타일위에 과외 노트가 놓여져 있다.

마지막 줄의 마지막 타일로 이동할 수 없는 경우가 존재할 수 있다. 이 경우에는 번호가 가장 큰 타일로 이동하면 된다.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄부터 N*N-N/2줄(/는 정수 나눗셈이다)에는 두 양의 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 6, 1 ≤ i ≤ N * N - N / 2) 타일 i의 왼쪽에 쓰여 있는 숫자는 Ai, 오른쪽에 쓰여 있는 숫자는 Bi이다.

 

출력

첫째 줄에 가장 짧은 경로의 길이 (타일의 개수)를 출력한다.

둘째 줄에는 경로 상의 타일의 번호를 공백으로 구분하여 순서대로 출력한다. 만약, 가장 짧은 경로가 여러 가지라면, 아무거나 출력하면 된다.

 

예제 입력

5
1 4
4 5
3 4
5 4
5 2
4 2
5 6
4 4
6 5
2 4
5 1
6 1
1 6
2 3
4 2
5 3
1 2
5 5
4 1
2 2
4 3
2 3
3 4

 

예제 출력

7
1 2 7 12 17 22 23

 

해결방법

BFS 탐색을 통해 최단거리를 찾는 문제이다

일반적인 문제와 다르게, 이동 조건과 맵의 모양이 아주 특이하다

참고 블로그 : https://rebas.kr/733

 

 

⭐️ 솔루션 ⭐️

map, ard 2차원 배열을 이용하여 도미노 타일의 정보와 타일의 번호를 저장하였다

이러한 정보를 이용하여 도미노 타일 간의 관계를 2차원 벡터로 변환한 뒤, BFS 탐색을 수행했다

1  4  4  5  3  4  5  4  5  2
0  4  2  5  6  4  4  6  5  0
2  4  5  1  6  1  1  6  2  3
0  4  2  5  3  1  2  5  5  0
4  1  2  2  4  3  2  3  3  4

1  1  2  2  3  3  4  4  5  5
0  6  6  7  7  8  8  9  9  0
10 10 11 11 12 12 13 13 14 14
0  15 15 16 16 17 17 18 18 0
19 19 20 20 21 21 22 22 23 23

 

처음에는 map, ard 2차원 배열만을 이용하여 BFS 탐색을 수행했다

해당 행과 열의 정보를 바탕으로 타일의 left 인지 right 인지 판별한 후, 탐색을 진행했다

코드가 좀 많이 복잡하고 난잡해져서 결국 구글링으로 솔루션을 검색했다

 

발견한 솔루션은 아래와 같다

1. map, ard 2차원 배열을 준비한다
2. 전체 map 을 돌며 4방향 탐색을 수행한다
3. 만약 타일의 번호가 같거나 맵을 벗어난다면 경우에서 제외시킨다
4. 만약 타일의 번호가 다르고 값이 같다면 이 두 타일은 인접했다고 할 수 있다. 따라서 2차원 벡터에 간선 정보를 넣어준다
5. 이 간선 정보를 이용하여 타일의 번호로 BFS 탐색을 수행한다
6. 탐색을 수행할 때, 타일의 번호의 최대값을 갱신시켜준다

 

 

 

소스코드

문제 해결 시간 : 2h 30m

메모리 : 24732 KB

시간 : 96 ms

#include <iostream>
#include <cstring>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX_R 501
#define MAX_C 1001
#define MAX_T 250000
using namespace std;

int n,num,last;
int map[MAX_R][MAX_C];
int adr[MAX_R][MAX_C];
int path[MAX_T];
bool visited[MAX_T];
vector<int> adj[MAX_T];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

void bfs(){
    queue<int> q;
    q.push(1);
    visited[1] = true;
    path[1] = -1;
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        last = max(last,now);
        
        for(int i=0; i<adj[now].size(); i++){
            int nxt = adj[now][i];
            
            if(!visited[nxt]){
                q.push(nxt);
                visited[nxt] = true;
                path[nxt] = now;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    // 입력
    num = 1;
    for(int i=0; i<n; i++){
        if(i%2 == 0){
            for(int j=0; j<2*n; j++){
                cin >> map[i][j];
                adr[i][j] = num;
                
                if(j%2 == 1){
                    num++;
                }
            }
        }else{
            for(int j=1; j<2*n-1; j++){
                cin >> map[i][j];
                adr[i][j] = num;
                
                if(j%2 == 0){
                    num++;
                }
            }
        }
    }
    
    // 인접한 노드를 벡터로 연결
    for(int i=0; i<n; i++){
        for(int j=0; j<2*n; j++){
            if(map[i][j] == 0) continue;
            int now = adr[i][j];
            for(int k=0; k<4; k++){
                int nx = i + dx[k];
                int ny = j + dy[k];
                int nxt = adr[nx][ny];
                
                if(nx<0 || ny<0 || nx>=n || ny>=2*n) continue;
                if(now == nxt) continue;
                
                if(map[i][j] == map[nx][ny]){
                    adj[now].push_back(nxt);
                }
            }
        }
    }
    
    // BFS 탐색
    memset(visited, false, sizeof(visited));
    last = 0;
    bfs();
    
    // 역으로 추적하여 경로 벡터 채우기
    vector<int> v;
    for(int pos=last; pos!=-1; pos=path[pos]){
        v.push_back(pos);
    }
    
    // 경로의 노드 개수 출력
    cout << (int)v.size() << "\n";
    
    // 경로 출력
    for(int i=(int)v.size()-1; i>=0; i--){
        cout << v[i] << " ";
    }
    cout << "\n";
    
    return 0;
}