전체 글361 [BOJ]2098번: 외판원 순회 문제: https://www.acmicpc.net/problem/2098 비트마스킹 + DP로 해결할 수 있습니다. dp 상태정의를 dp[현재까지 방문한 상태][현재 노드]로 하고 점화식은 아래와 같이 세울 수 있습니다. dp[nxtState][nxtNode] = min(dp[nowState][nowNode] + cost[nowNode][nxtNode]) 방문 상태를 저장함으로써 중복 방문을 없앨 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ2098.java 2022. 5. 1. [BOJ]16946번: 벽 부수고 이동하기 4 문제: https://www.acmicpc.net/problem/16946 BFS + 아이디어가 필요한 문제입니다. NM 값이 100만이므로 벽 갯수만큼 BFS를 돌려보면 시간초과가 납니다. 그러므로 BFS를 도는 횟수를 줄여야합니다. 해결한 아이디어는 다음과 같습니다. ex. 빈 칸끼리 붙어있는 값을 '컴포넌트'라고 하겠습니다. 1. 전체 BFS를 1번 돌면서 빈 칸으로 이뤄져있는 모든 컴포넌트 정보를 (컴포넌트번호, 컴포넌트 내 빈 칸 갯수) 저장합니다. 2. 1번 연산을 마친 다음에 모든 벽에 대해 벽이 있는 해당 칸과 인접한 4칸에 존재하는 컴포넌트 갯수를 더해줍니다. 1번에서 빈 칸 갯수 외에 '컴포넌트 번호'를 굳이 저장한 이유는 인접한 4칸을 탐색할 때 동일한 컴포넌트에 포함되는 빈 칸을 중.. 2022. 5. 1. [BOJ]1197번: 최소 스패닝 트리 문제: https://www.acmicpc.net/problem/1197 MST 기본 문제입니다. union-find 알고리즘을 사용하여 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1197.java 2022. 4. 29. [BOJ]1167번: 트리의 지름 문제: https://www.acmicpc.net/problem/1167 트리의 지름은 두 단계를 통해서 구할 수 있습니다. 1. 임의의 노드에서 가장 먼 노드 K 찾기 2. 노드 K에서 가장 먼 노드까지의 거리 D 구하기 그러면 D가 정답이 됩니다. 해당 문제는 노드 간 거리가 주어져 있으므로 다익스트라 연산을 두 번하면 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1167.java 2022. 4. 28. 이전 1 2 3 4 5 ··· 91 다음
