본문 바로가기

Algorithm/BOJ172

[BOJ]4195번: 친구 네트워크 문제: https://www.acmicpc.net/problem/4195 단순 DFS로 탐색하면 시간초과로 터지는 문제입니다. Union & Find를 통해 해결했습니다. 풀이는 jason님 (https://jason9319.tistory.com/41) 링크를 참고했는데요. 일반 Union & Find 보다 한 단계 더 나아가 자식의 숫자를 저장하고 있어야 합니다. 그러므로 문제가 생기는 부분이 있습니다. 바로 friend1, friend2 로 들어오는 관계가 이미 부모 - 자식 관계인 경우 입니다. BEFORE의 경우 무조건 부모쪽에 더하도록 만들어주었고, AFTER는 부모 - 자식 관계인 경우 부모를 리턴, 부모 - 자식 관계가 아닌 경우 더하도록 만들었습니다. BEFORE 코드가 문제가 되는 이유는.. 2020. 8. 11.
[BOJ]16397번: 탈출 문제: https://www.acmicpc.net/problem/16397 단순 BFS 문제입니다. 중복 방문하지 않도록 이미 탐색해본 숫자는 VISITED 배열에 저장해주면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ16397.java 2020. 8. 6.
[BOJ]9019번: DSLR 문제: https://www.acmicpc.net/problem/9019 BFS 문제입니다. 숫자로 처리하지 않고 문자열로 처리하다가 시간초과가 났습니다. 숫자 처리하는 방법은 jaimemin님 블로그 포스팅을 참고하였습니다. (https://jaimemin.tistory.com/654) 시간초과가 난다면, 문자열로 처리하는 부분을 숫자로 바꿔주면 될 것입니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ9019.cc 2020. 7. 30.
[BOJ]1162번: 도로포장 문제: https://www.acmicpc.net/problem/1162 JusticeHui님이 푸신 솔루션을 참고하여 해결하였습니다. (출처: https://justicehui.github.io/usaco/2019/07/12/BOJ1162/) 도로 포장에 대한 정보를 어떻게 나타내느냐가 중요한 문제입니다. 이 문제의 경우 다익스트라의 결과값인 dist[N]을 다음과 같이 응용해서 정의할 수 있습니다. dist[N][K]: 출발점 1번 도시에서 N번 도시까지 갈 때, K개의 도로를 포장해서 가는 최단거리. 이 때 저희가 원하는 정답 값은 아래와 같습니다. answer = min(dist[N][0],dist[N][1],dist[N][2],dist[N][3],dist[N][4],...,dist[N][K]) .. 2020. 7. 29.

티스토리툴바