Algorithm/Graph
-
백준 14502 - 연구소Algorithm/Graph 2024. 4. 4. 11:26
14502번: 연구소 (acmicpc.net) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제를 살펴보면, 0인 곳으로 2(바이러스)가 퍼져나가는 시스템이다. 그렇다면 bfs를 이용해서 경로를 찾아나가면서 0을 따라서 2(바이러스)로 변경시켜주면 좋겠다는 생각을 우선 하게 되었다. 일단 먼저 바이러스를 퍼트리는 bfs 함수를 구현해보자. def bfs(temp): q = deque() for i in range(n): for j in range(m): if temp[i][j] == 2: q.append((i, j)) ..
-
백준 1949 - 우수 마을Algorithm/Graph 2024. 3. 5. 15:13
1949번: 우수 마을 (acmicpc.net) 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 문제 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접..
-
백준 1174 - 우주신과의 교감Algorithm/Graph 2024. 1. 14. 11:29
1774번: 우주신과의 교감 (acmicpc.net) 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 문제를 살펴보면서 "새로 만들어야 할 정신적인 통로의 길이들이 합이 최소가 되게 통로를 만들어 “빵상”을 외칠수 있게 도와주자." 이 문장과 좌표들을 입력받는 것을 통해 거리의 합을 구하고, 최소가 될 수 있는 통로를 만들어주어야 한다고 생각했다. 문제를 보면 예전에 풀어보았던 최소 스패닝 트리 문제가 떠오르게 되어, 전체적인 알고리즘을 최소 스패닝 트리 문제와 동일하게 가져갔다. ..
-
백준 1956 - 운동Algorithm/Graph 2024. 1. 7. 13:02
1956번: 운동 (acmicpc.net) 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 이 문제를 처음보고 solved.ac에서 본 그래프 문제들과 굉장히 유사한 문제라는 생각이 들게 되었다. 그 문제들도 cost, start, end를 설정해서 list 형태로 append 시켜놓고, 알고리즘을 사용하게 되는데, 이 때 graph 알고리즘이라면 BFS, DFS 등이 있을 수 있겠지만, 나의 첫번째 접근은 "도로의 길이의 합이 최소"라는 지점에 착안하여 다익스트라 알고리즘을..