본문 바로가기

공부/알고리즘 문제풀이

[BOJ] 5213. 과외맨

반응형

과외맨

클릭시 이동합니다.


어떻게 풀까?


굉장히 힘들었습니다.

우선, 문제의 절반이 별로 문제 푸는데 도움이 안된다는 사실에 좌절했습니다. 허허


이 문제는 BFS문제이지만, 단계를 잘 설정해서 수행해야 한다는 것이 중요합니다.

문제를 풀기 위해서 생각해야 할 것들에 대해서 생각해 봅시다.


1. 타일들 간에 이동가능한 인접 행렬을 만들어야 합니다.

2. BFS를 통해서 최단 거리를 찾습니다.

3. 최단 거리를 찾는 경로를 어떻게 출력할지 생각해야 합니다.


이 중에서 가장 어려운 것은 1번 입니다.


타일을 어떻게 붙일지에 대해서 생각해 봅시다!


일단, 약간 귀찮은 점은 홀수행과 짝수행에서 타일의 개수가 다르다는 것입니다!


우선은, 타일을 모두 왼쪽으로 밀어넣어서 생각해봅시다!

또한, 타일에 여러 정보가 있기 때문에 따로 구조체를 만들어서 타일을 관리합시다!!


타일의 구조체는


{

위치

타일의 번호

타일의 왼쪽 값,

타일의 오른쪽 값

}


이렇게 될 것입니다!


이렇게 하면, 이제 타일이 어떻게 이동하는지 파악하기 꽤나 편해집니다.


자, 그럼 이제 타일의 인접 배열을 만들 시간입니다!

그럼 우선, 타일이 어떻게 이동할 수 있는지 확인해봅시다.


우선, 타일을 왼쪽으로 밀어놓으면 아래와 같은 모양으로 저장될 것입니다.




그리고, 이렇게 저장된 타일들은 왼쪽 위부터 오른쪽으로 이동하면서 타일 번호를 하나씩 부여받습니다.


그렇다면, 타일이 이동하는 방향은 어떻게 알아낼 수 있을까요!?


우선, 하나의 타일이 이동할 수 있는 방향을 봅시다!



우선, 타일의 왼쪽 숫자와 걸쳐지는 곳은 왼쪽 위, 왼쪽, 왼쪽 아래 3군데 입니다.

마찬가지로, 타일의 오른쪽 숫자와 겹치는 쪽은 타일의 오른쪽 위, 오른쪽, 오른쪽 아래로 3 군데입니다.


이 상황을 한번 왼쪽으로 밀어넣은 맵에서 확인해봅시다.



오호, 위 사진을 보니 타일의 6 방향은

현재 타일의 좌표를 (r,c)라고 했을 때,

(r-1,c), (r-1,c+1), (r,c-1), (r,c+1), (r+1,c), (r+1, c+1) 6방향을 확인하면 될 것이라는 생각이 듭니다!


하지만, 일단 홀수행과 짝수행의 개수가 다르다는 것을 알고 있습니다.

이번에 짝수행을 봤으니, 한번 홀수행을 봅시다!



이번엔, 3 번째 행에 있는 2번째 열 타일을 보겠습니다!

이동할 수 있는 방향은 위의 그림과 같고, 이를 타일들의 배열에서 찾아봅시다.




세상에나! 차이점을 아시겠나요?


홀수 행에서는 위, 아래를 봐야하는 배열이 살짝 달라집니다!


짝수 행에서는 (r-1,c), (r-1,c+1), (r,c-1), (r,c+1), (r+1,c), (r+1, c+1) 6 방향이었지만,

홀수 행에서는 (r-1,c), (r-1,c-1),  (r,c-1), (r,c+1), (r+1,c), (r+1, c-1) 6 방향 입니다!!!


홀수 행일때는 저 위의 방향을 살피고, 짝수 행일때는 아래의 방향을 체크해주고... 연산이 매우 복잡해집니다.

하지만, 약간의 발상의 전환을 통해 문제를 쉽게 해결할 수 있습니다.


타일의 이동 방향을 그냥 8 방향으로 늘리는 것입니다!

만약 행이 홀수라면, 오른쪽 위, 오른쪽 아래에 있는 타일은 무조건 이동 불가능한 것으로 체크해주고,

만약 행이 짝수라면, 왼쪽 위, 왼쪽 아래에 있는 타일은 무조건 불가능한 것으로 체크해주면 됩니다.


그러면 이제 문제의 조건에 따라서, 행의 짝, 홀 여부를 통해서 타일마다 인접 행렬을 만들 수 있습니다!


이제 2번 단계를 프로그래밍해 봅시다.


위의 1번 단계를 잘 만들어놨으면, 평범한 BFS 문제가 됩니다!

자신이 지나온 곳의 노드를 visit 체크 해주고, 다음으로 갈 수 있는 경로를 확인해 주어서 큐에 넣어줍니다.


다만, 약간 생각해봐야 할 것이 있습니다. 

바로, 도착점에 가지 못할 경우가 있기 때문이죠.

도착점에 가지 못할 경우에는 가장 높은 번호의 타일으로 가는 최소 경로를 출력하라고 합니다!


우선, 오른쪽 아래에 있는 타일일수록 타일의 번호가 높다는 것을 알 수 있습니다.

그리고, 도착점에 도착하지 못할 경우에는 타일의 번호가 높은 곳으로 도착할 수 있는 경로를 나타내죠.


결국, 도착할 수 있는 가장 높은 타일 번호의 경로를 출력하면 어떤 조건이든 다 통과할 수 있는 것 입니다.


이 경로는 어떻게 구하면 될까요?

이는 bfs의 특성을 이용하면 됩니다!





위와 같은 그래프가 있다고 합시다!

초록색 노드에서부터 출발하겠습니다!




우선 bfs를 한번 돌면 위와 같이 될 것입니다!

한번 방문했기 때문에 다시 반복적으로 방문하지 않기 위해서 비짓처리를 해주었습니다! 빨간색은 이제 더이상 해당 노드로 접근을 할 수 없다는 것입니다! 최단거리를 구하는 것이기 때문에 더 이상 방문해봤자 더 빨라질리는 없는 것이죠!



아래 그림과 같이 해당 노드로 이동하려고 해도, 이미 방문처리가 되어있기 때문에 더이상 해당 노드로 이동할 수 없습니다!

즉, 이미 한번 방문했던 노드에는 다른 노드가 전혀 개입하지 못한다는 것이죠!


이런 특성을 이용하면, 도착점에서의 노드 번호만으로 어떻게 노드를 방문했는지에 대한 경로를 구할 수 있습니다!


바로 어떤 노드를 방문했을 때, 해당 노드를 향했던 노드의 번호를 따로 저장하는 배열을 만들어 놓는 것이죠.

어짜피, 이미 방문한 노드에 다른 노드가 왔을 때, 다른 노드들은 해당 경로배열을 업데이트 시키지 못하기 때문에,  해당 배열에는 계속해서 최소 경로로 향하는 노드가 저장되어 있습니다.


이 노드들을 따라가면, 결국 시작점의 위치가 나오게 되는 것이죠!!!


좀 더 자세히 알아보기 위해 위의 예에서 몇가지 상황을 더 보겠습니다.

그리고, 해당 노드에 저장된 이전 경로를 파란색 화살표로 나타내겠습니다! 



아까 위의 상황에서, 이미 오른쪽 아래의 노드는 방문된 상태이기 때문에, 아무런 업데이트를 수행하지 않고, 왼쪽 아래의 노드를 방문합니다!

왼쪽 아래의 노드는 아직 아무런 방문이 이루어지지 않았기 때문에, 거리는 2가 됩니다!



그리고, 이렇게 업데이트가 되겠죠!




그리고 이제 오른쪽 아래 노드가 왼쪽 아래로 가는 노드로 방문을 시도하겠지만, 이미 방문된 지점이기 때문에 아무런 일이 일어나지 않습니다.


그렇다면 이제 경로를 한번 출력해볼까요!?


왼쪽 아래의 노드의 경로를 보겠습니다.

왼쪽 아래의 노드에 연결된 파란색 선을 따라가면 가운데 노드가 나오고, 가운데 노드의 파란색 노드를 따라가면 시작점이 나옵니다!

이렇게, 한 노드를 처음 방문 했을때, 어떤 노드에서 방문했는지만 저장해주면, 이 경로를 역추적하여 경로를 알아낼 수 있습니다!!!


BFS에서 해당 점을 방문했을 때, 현재 노드를 now, 다음에 큐에 넣을 노드를 next라고 한다면,

path[next] = now를 통해서 이전 경로들을 저장할 수 있습니다.


그리고, 방문할 수 있는 제일 높은 타일의 번호를 저장만 해놓는다면, 마지막에 해당 타일의 번호를 역추적해서 경로를 나타낼 수 있습니다!!


코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<cstdio>
#include<queue>
using namespace std;
struct TILE{
    int l, r;
    int tnum;
    TILE(){
        l = r = -1;
    }
};
 
TILE tile[502][502];
bool visit[502][520];
struct INFO{
    int r, c, tnum;
};
 
int dr[8= {-1,1,1,-1,1,-1,0,0};
int dc[8= {0,0,1,1,-1,-1,-1,1};
bool adj[502][502][8];
int path[250010];
int st[250000], top;
int main(){
    int n;
    int cnt = 1;
    scanf("%d\n"&n);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n - 1 + (i&1); j++){
            scanf("%d %d\n"&tile[i][j].l, &tile[i][j].r);
            tile[i][j].tnum = cnt++;
        }
    }
 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <=- 1 + (i&1); j++){
            for(int d = 0; d < 8; d++){
                int nr = i + dr[d];
                int nc = j + dc[d];
                if(tile[nr][nc].l == -1continue;
                switch(d){
                    case 2:
                    case 3:
                    if((i&1== 0){
                        adj[i][j][d] = tile[i][j].r == tile[nr][nc].l;
                    }
                    break;
                    case 0:
                    case 1:
                    if((i&1)){
                           adj[i][j][d] = tile[i][j].r == tile[nr][nc].l; 
                    }
                    else{
                        adj[i][j][d] = tile[i][j].l ==tile[nr][nc].r;
                    }
                    break;
                    case 4:
                    case 5:
                    if((i&1)){
                        adj[i][j][d] = tile[i][j].l == tile[nr][nc].r;
                    }
                    break;
                    case 6:
                    adj[i][j][d] = tile[i][j].l ==  tile[nr][nc].r;
                    break;
                    case 7:
                    adj[i][j][d] = tile[i][j].r == tile[nr][nc].l;
                    break;
                }
 
            }
        }
    }
 
    int max = 0;
    queue<INFO> que;
    INFO info;
    info.r = 1;
    info.c = 1;
    info.tnum  = 1;
 
    que.push(info);
    path[1]= 0;
    int pathnum;
 
    visit[1][1= true;
    while(!que.empty()){
        INFO now = que.front();
        que.pop();
        
        max = now.tnum > max ? now.tnum : max;
 
        for(int d = 0; d < 8; d++){
            int nr = now.r + dr[d];
            int nc = now.c + dc[d];
 
            if(adj[now.r][now.c][d]){
                INFO next;
                next.r = nr;
                next.c = nc;
                next.tnum = tile[nr][nc].tnum;
                if(visit[nr][nc]) continue;
                visit[nr][nc] = true;
                path[next.tnum] = now.tnum;
                
                que.push(next); 
            }
        }
 
    }
        int p = max;
        while(p){
            st[top++= p;
            p = path[p];
        }
        printf("%d\n", top);
        while(top){
            printf("%d ", st[--top]);
        }
        printf("\n");
    return 0;
}
cs


여담


간선의 개수가 최대 6*타일의 개수 이기 때문에,

시간 복잡도는 입니다.





반응형