https://www.acmicpc.net/problem/1649
1649번: 택시
첫 번째 줄에 교차로의 개수인 N(1<=N<=1,000)과 도로의 개수 M이 주어진다. 그 다음 M개에 줄에는 도로의 정보를 알려주는 시작점과 끝점이 주어진다. 다음 줄에는 시작점 A와 끝점 B, 그리고 방문해야할 중간 지점의 개수 K개 주어진다. 마지막 줄에는 공백을 구분으로 C1, C2, …, Ck가 차례대로 주어진다.
www.acmicpc.net
이번 문제는 위상정렬과 관련된 문제이다.
4일동안 고민하다가, 결국 Github에 공유된 정답 코드를 보았다.
좋은 코드를 올려주신 kks227님께 감사를 드리며...
https://github.com/kks227/BOJ/blob/master/1600/1649.cpp
kks227/BOJ
BOJ source codes (too late. when I made this, I had already solved 1,100 problems...) - kks227/BOJ
github.com
우선 이 문제의 핵심은, 위상정렬을 이용해서 풀지 않으면 메모리 초과나 시간 초과가 무조건 발생한다.
따라서, 이 문제는 무조건! 위상 정렬을 이용해서 풀어야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
while(!Q.empty()){
int curr = Q.front();
Q.pop();
if(C.find(curr) != C.end()) cnt[curr]++;
for(int next: adj[curr]){
if(cnt[next] == cnt[curr]) val[next] += val[curr];
else if(cnt[next] < cnt[curr]){
cnt[next] = cnt[curr];
val[next] = val[curr];
}
if(--in[next] == 0) Q.push(next);
}
}
|
이 문제의 핵심 코드는 이 부분이다.
우선 문제의 변수들을 하나씩 설명하면,
Q = queue<int>
cnt[i] = i 교차로까지 C1 ~ Ck중 방문한 교차로의 수
val[i] = i 교차로까지 경로의 수
처음 선언 시, cnt와 val 모든 원소들은 0으로 초기화가 되어 있다.
val[A] = 1으로 값을 넣어줘야 하는 이유는, val의 값의 연산은 모두 기존의 값을 바탕으로 이용하므로 1로 초기화해줘야 한다.
위상 정렬을 위한 처음 시작 아이템을 찾기 위해서, in[i] 값이 0인 것을 찾고 while문안으로 들어간다.
while문안에 동작을 이해하는 것이 가장 중요하다!
if(C.find(curr) != C.end()) cnt[curr]++;
>> 이 부분은 C1 ~ Ck가 들어있는지 확인하는 부분이다. 교차로들은 모두 일방통행으로 구성되어 있으므로, 한번 방문된 Ci는 절대로 방문되지 않는다고 생각하면 된다.
for(int next: adj[curr]){
if(cnt[next] == cnt[curr]) val[next] += val[curr];
else if(cnt[next] < cnt[curr]){
cnt[next] = cnt[curr];
val[next] = val[curr];
}
if(--in[next] == 0) Q.push(next);
}
>> if(cnt[next] == cnt[curr])은 현재 curr 교차로에서 방문된 C1 ~ Ck의 값이, next 교차로에서 방문된 C1 ~ Ck의 값과 같다면, 경로의 수를 더할 수 있다는 것을 의미한다.
여기서 가질 수 있는 의문 점은,
'cnt[next]와 cnt[curr]의 값이 같다는 게 방문한 C1 ~ Ck의 노드도 같다고 할 수 있을까?'라는 의문이 생길 수 있다.
cnt[next] = 3, cnt[curr] = 3이라고 생각해보자!
next > C1, C2, C3
curr > C1, C2, C4
C1, C2, C4 순서로 방문하는 것이 불가능하다면 이유는, C1 -> C2 -> C3 -> C4 위상을 이루고 있을 경우이다. 즉, 교차로 방문 순서가 맞지 않기 때문이다. C3을 거치지 않고, C4로 방문하는 것은 불가능하다.
방문하는 것이 가능하다면 이유는,
C1 -> C2 -> C3, C4의 형태로 위상이 이루어진 경우 가능하다. 하지만, 이 경우에 대해서는 cnt[B] < K의 형태가 되므로 경로가 없는 경우에 해당할 것이다.
추가적으로 cnt[next]가 0이 아닌 값을 가질 수 있을까?
next 교차로는 cur 교차로 이외에도 다른 교차로에 의해서 방문될 수 있으므로 값을 가질 수 있다.
else if(cnt[next] < cnt[curr]){
cnt[next] = cnt[curr];
val[next] = val[curr];
}
>> 교차로 curr에서 현재 C1 ~ Ck 방문된 값이 교차로 next의 값보다 크다면, next의 cnt와 val 값을 갱신해야 한다. 여기서 else는 할 필요가 없는게, cnt[next] > cnt[curr]이라면, 교차로 next의 cnt와 val 값을 건드리면 안된다.
위의 해설에서 의문이 생길 수 있는 대부분은 모든 노드들은 일방통행 및 위상정렬 형태를 이루고 있을 것이라고 떠올리면 해결할 수 있다.
이 문제는, 4일동안 짬을 내서 해결할려고 노력했지만 실패했다.
실패의 원인은 , 위상 정렬을 이용하지 않고 풀려고 했던 것이 문제가 아니였을까
'알고리즘 > 백준' 카테고리의 다른 글
| 15927번 : 회문은 회문아니야!! (0) | 2020.01.27 |
|---|---|
| 2167번: 2차원 배열의 합 (0) | 2020.01.27 |
| [15686번] 치킨 배달 (0) | 2019.10.19 |
| [15683번] 감시 (0) | 2019.10.19 |
| [17472번] 다리 만들기 2(C++, 삼성 상시 테스트, 쉬운 설명) (0) | 2019.10.19 |