본문 바로가기

BOJ75

[BOJ]16947번: 서울 지하철 2호선 www.acmicpc.net/problem/16947 DFS/BFS 문제입니다. 싸이클 판별만 잘 하게 되면 DFS로 탐색하든 BFS로 탐색하든 상관없습니다. 싸이클 내부에 있는 노드의 성질은 자기 자신에게 들어오는 간선이 최소 1개이상 입니다. 이 점을 활용하여 그래프를 입력받을 때 1. 자기 자신에게 들어오는 노드를 세주기 2. 싸이클의 후보가 아닌 노드를 제거하면서 그 노드과 연결되어 있는 노드의 간선 갯수를 하나씩 빼줍니다. 3. 이렇게 갱신을 하다가 더 이상 갱신되지 않으면 남아있는 노드들은 전부 싸이클에 속합니다. 이 점을 활용해서 순환선 내부에 있는 역을 파악하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ16947.cc 2020. 9. 9.
[BOJ]9328번: 열쇠 https://www.acmicpc.net/problem/9328 jaimemin님 풀이를 참고하여 해결하였습니다. (https://jaimemin.tistory.com/692) 문제 풀이에 필요한 아이디어는 아래와 같습니다. 1. 모든 칸에서 입장이 가능하다는 조건을 위해 주어진 그래프 테두리에 빈 칸을 추가해서 모든 칸 방문하게 하기 2. 열쇠를 새로 얻으면 그 지점부터 bfs를 다시 시작합니다. 3. 열쇠나 문서를 얻었으면 재방문을 막기 위해 빈 칸으로 바꿔버립니다. 위와 같은 기법을 통해 bfs를 돌리면 문제를 해결할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ9328.cc 2020. 9. 1.
[BOJ]10217번: KCM Travel https://www.acmicpc.net/problem/10217 바킹독님 풀이를 통해서 해결했습니다. (https://blog.encrypted.gg/164) DP[i][j]: "1번 노드부터 i번 노드까지 비용 j를 써서 갈 때의 최소 시간"으로 상태를 정의합니다. 예외 조건은 j 값이 M을 초과하면 예외입니다. (continue) 이렇게 상태를 정의하고 1번 노드부터 다익스트라를 돌리면, "비용 M 이하" 조건을 만족하는 경로 중에서 가장 먼저 N번 노드에 도착하는 경로가 최소 시간을 만족하는 정답입니다. https://github.com/cottory/algorithm/blob/master/BOJ/BOJ10217.cc 2020. 8. 17.
[BOJ]1039번: 교환 문제: https://www.acmicpc.net/problem/1039 BFS 문제입니다. 예외조건 때문에 많이 틀렸네요. 세 가지 주의점이 있습니다. 1. 바뀐 후의 숫자가 0으로 시작하면 안됩니다. 2. 10,20,30처럼 두 자리수이면서 0으로 끝나는 숫자는 Swap하면 안됩니다. (단, 100,1000,10000 같은 숫자들은 괜찮습니다. 0 끼리 바꾸면 되니까요) 3. 총 K번 Swap 회차만큼 Swap을 할텐데, 각 회차가 될 때 마다 방문배열을 초기화해줘야 합니다. 무슨 말이냐면 이전에 나왔던 숫자가 나중에 나와도 됩니다. 이를 위해서 저는 매 루프를 while (!q.empty()) 가 아니라 while (q.size()--) 만큼만 돌았습니다. 코드: https://github.com/.. 2020. 8. 13.

티스토리툴바