graph32 [Problem Solving] BOJ 6593: 상범 빌딩 문제 출처: https://www.acmicpc.net/problem/6593 출발지, 목적지, 장애물이 주어져있을때, 출발지에서 목적지까지 도달하는데 걸리는 최소비용을 구하는 문제이다. 2차원 -> 3차원으로 차원을 하나 더 늘리면된다. 2차원에서 진행하는것과 다를 게 없다. BFS를 수행하는 데, 핵심은 dist[next] > dist[cur] + 1이라면 dist[next] = dist[cur] + 1로 갱신하는 것이다. BFS수행이 끝난 후 dist[end]가 무한대가 아니라면 Escaped In... 를 출력하고 무한대라면 Trapped!를 출력한다.#include #include #include #include #include #include #include #define endl '\n'.. 2025. 7. 14. [Problem Solving] BOJ 2668: 숫자고르기 문제 출처: https://www.acmicpc.net/problem/2668 그래프에 존재하는 모든 사이클에 있는 노드들의 개수와 그 노드들을 오름차순으로 출력하는 문제이다. 이 문제는 dfs로 해결할 수 있다.dfs는 start, cur, visited를 매개변수로 받는다.dfs는 start가 사이클에 해당하는 노드인지 판단하는 함수이다.매 dfs 시작 시 방문할 노드를 판단하기 위한 visited 배열을 만들어서 dfs에 넘겨준다.dfs 수행 중 next_node가 start와 같다면, 그 노드는 사이클에 포함되는 노드이므로 result에 추가하고 dfs를 종료한다. (Java의 TreeSet은 순서대로 정렬되는 집합이다.) import java.io.BufferedReader;import java.. 2025. 7. 7. [Problem Solving] BOJ 14938: 서강그라운드 문제 출처: https://www.acmicpc.net/problem/14938 i번째 노드가 t[i]의 값을 가지고 있는 양방향 그래프가 있을 때, 어느 한 노드에서 출발하여 가중치의 합이 m이하가 되도록 하여 방문할 수 있는 노드들의 t[i]의 합의 최댓값을 구하는 문제이다. 문제 조건을 보면 제한시간은 1초이고, 노드의 최대 개수는 100개 이므로, 모든 쌍의 최단 거리를 구할 수 있는 플로이드 워셜 알고리즘을 사용해서 풀 수 있는 문제이다. 1. 플로이드 워셜 알고리즘을 수행해서 모든 노드 쌍의 최단 거리를 계산한다.2. 1번 노드부터 시작해서 n번 노드 까지 가중치의 합이 m이하가 되도록 하여 방문할 수 있는 노드들의 t[i]의 합을 temp에 저장한다.3. answer = max(temp, a.. 2025. 6. 24. [Problem Solving] BOJ 2458: 키 순서 문제 출처: https://www.acmicpc.net/problem/2458 N명의 학생이 있다.M개의 대소관계를 입력 받는데,a b는a번 학생이 b번 학생보다 작다는 의미이다.이렇게 M개의 관계를 입력 받았을 때, 자신의 키 순서를 확실히 알 수 있는 학생의 수를 구하는 문제이다. a번 학생이 b번 학생보다 작을 때, 그래프에서 a노드에서 b노드로 향하는 간선을 만든다. 그 다음 벨만포드 알고리즘을 수행해서 dist 행렬을 만든다. i번째 학생이 자신의 키 순서를 확실히 안다는 것은, 모든 j번째 학생에 대해서 i -> j로 도달 가능하거나, j -> i로 도달 가능해야 한다는 것이다. 만약 i -> j로 도달할 수 없고, j -> i로 도달할 수도 없다면 i번째 학생은 자신의 키 순서를 확실히 알 .. 2025. 5. 30. [Problem Solving] BOJ 17142: 연구소 3 문제 출처: https://www.acmicpc.net/problem/17142 N*N 격자가 있다.0: 통로1: 벽2: 바이러스이다. 바이러스 중에서 활성화된 바이러스를 M개 골랐을 때, 벽이 아닌 공간에 모두 퍼지는 시간의 최솟값을 구하는 문제이다.모든 조합에 대해서 다음을 수행한다.1. 조합을 고른다.2. N*N distance의 모든 원소를 무한대로 설정한다.3. 조합에서 각각의 바이러스 지점에서 bfs를 수행한다. (바이러스는 벽이 아닌 모든 곳으로 퍼질 수 있다.)4. 격자에서 모든 통로, 그리고 활성화된 바이러스 지점에 바이러스가 퍼질 때 까지 걸리는 최소 시간 중 최댓값을 구한다.5. 4에서 구한값과 이전 조합에서 구한 값을 비교해서 벽이 아닌 공간에 모두 퍼지는 시간의 최솟값을 갱신한다.. 2025. 5. 12. [Problem Solving] BOJ 17471: 게리멘더링 문제 링크: https://www.acmicpc.net/problem/17471 그래프에서 지역구를 두 개로 나눈다. 한 지역구에는 적어도 하나의 노드를 가져야 하고, 한 지역구의 노드들을 하나의 연결요소여야 한다. 일단 모든 노드를 방문하는 bfs를 수행하는 데, bfs 호출 횟수가 3번 이상이라면, 그래프가 3개 이상으로 쪼개져있어서 두 개의 지역구로 나누는 것이 불가능 하다. 이 때는 -1을 출력하고 프로그램을 종료한다. bfs 호출 횟수가 정확히 2번이라면, 쪼개진 두 개의 그래프의 노드의 인구의 합의 차이가 답이 된다. bfs 호출 횟수가 정확히 한 번이라면, 전체 노드를 두 쪽을 내는 모든 경우의 수를 따져야한다.노드 집합을 분리해서 하나는 v1에 다른 하나는 v2에 저장한다.v1의 노드들이 .. 2025. 3. 30. 이전 1 2 3 4 ··· 6 다음