백준 2252
1) 백준 2252 : 줄 세우기 (https://www.acmicpc.net/problem/2252)
우선 열심히 그래프 그려가면 topological sort 생각하며 DFS와 함께 풀었고, 결론적으로 틀렸다.
왜 틀린지는 어떤 케이스에서 틀렸는지 찾다가 포기했다. 아까우니까 아래쪽에 기록은 하겠다.
< 맞는 방법 >
맞는 방법은 큐와 BFS를 활용하여 우선순위대로 출력하는 것이다.
우선 집중할 것은 cin >> a >> b에서 b는 다른 것에 비해 우선순위가 밀리는 점이다.
따라서 이들에게는 우선순위를 증가시켜서 나중에 출력되도록 한다(우선순위: 낮을 수록 좋은거)
그리고 bfs도중 우선순위가 0이 되지 않으면 큐에 넣지 않도록 한다.
이렇게 되면 우선순위가 낮은 수인 것일수록 먼저 큐에 들어가게 된다.
그래서 조건을 맞추며 클리어하게 된다.
< 틀린 방법 >
틀린 알고리즘은 다음과 같다.
adj list를 입력값을 통해 만들고, 그래프를 그린다. (다만 그래프 방향성을 거꾸로 한다.)
cin >> a >> b에서 a에 들어오는 입력값은 언제나 먼저될 권한을 가지기 때문에...
말로 설명이 잘 안된다. 그걸 잘 해야 하는데 말이다.
예를 들어
8 3
7 6
8 1
1 3 의 입력이 있다면,
7 -> 6 / 8 -> 1 -> 3 의 순서가 지켜져야 한다.
나는 역순으로 이것들을 정렬하고 마지막에 또 이를 거꾸로 뒤집을 것이기 때문에 7, 8, 1은 dfs의 시작값으로 우선 선택될 수 없다. 이들을 제외한 나머지 n까지의 숫자를 dfs하기 위해 벡터의 0번째에 push한다.
이후 벡터의 0번째 element를 기준으로 dfs()를 돈다.
그렇다면 0번 vector에넌 2 3 4 5 6이 들어가 있게 되고, v[3]에는 1이, v[1]에는 8이, v[6]에는 7이 있다.
따라서 출력은
2 3 1 8 4 5 6 7 이 된다.
이것을 거꾸로 출력하면 7 6 5 4 8 1 3 2로 조건에 적합한 수가 된다.
근데 통과 못했다.
https://github.com/JangJuMan/2019-winter-PS/12_2252.cpp
끗..ㅠ
