본문 바로가기

문제 해결/BOJ117

[백준] 학교 탐방하기 https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net MST 문제입니다. 최악, 최선의 피로도를 구해야하는데 최악의 경우에는 내리막길(0), 최선의 경우에는 오르막길(1)이 먼저나오도록 간선들을 정렬해서 크루스칼을 돌려주면 됩니다. import sys sys.stdin = open("input.txt", "r") input = sys.stdin.readline n, m = tuple(map(int, input()... 2023. 3. 21.
[백준] 동방 프로젝트(large) https://www.acmicpc.net/problem/14595 14595번: 동방 프로젝트 (Large) 첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다. www.acmicpc.net 유니온-파인드를 활용하여 해결하였습니다. 범위가 입력으로 들어오면 범위 안에 있는 방들을 합쳐주어야하는데 이미 합쳐진 방들을 다시 합치는 경우를 위해서 합쳐진 방의 대표 방을 정하고 대표 방이 합쳐진 방들의 범위를 range_dict에 저장하게 됩니다. 따라서 방을 합쳐줄 때에도 대표방이 포함하고 있는 방들을 뛰어넘어서 합쳐주어야 시.. 2023. 3. 20.
[백준] 나만 안되는 연애 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 대학에서 다른 대학으로 모두 이동이 가능해야하고 모든 간선의 합이 최소가 되어야하므로 최소 스패닝 트리를 찾아야함을 알 수 있습니다. 조건에 의해 남초 - 남초, 여초 - 여초를 연결하는 간선은 힙에 넣지 않고 크루스칼을 돌리면 됩니다. 그리고 마지막에 모든 정점들이 같은 집합에 속해있는지만 체크해주면 됩니다. import sys, heapq sys.std.. 2023. 3. 19.
[백준] 영우는 사기꾼? https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 필요한 건물이 다 지어졌는지를 체크하기 위한 in_node와 현재 건물의 개수에 대한 정보를 가지고 있는 building_cnt 배열을 활용하여 풀이하였습니다. 건물이 새로 하나 생기는 경우에 해당 건물에 영향을 받는 건물의 in_node를 1 감소시키고 건물이 하나도 없어지는 경우에는 해당 건물에 영향을 받는 건물의 in_node를 1 증가시켜주어야합니다. 그리고.. 2023. 3. 18.
[백준] 개미굴 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 간단한 트라이 문제입니다. dict를 활용하여 연결되는 개미굴을 이동할 때마다 dict도 같이 이동하면서 없는 경우에는 dict를 생성해주면 된다. 출력을 할때에는 dict의 key들이 먹이들이 되므로 key들을 정렬하여 dfs로 탐색하면서 출력해주면 됩니다. import sys, heapq from collections import deque, defaultdict sys.setr.. 2023. 3. 17.
[백준] 스크루지 민호 2 https://www.acmicpc.net/problem/12978 12978번: 스크루지 민호 2 구두쇠로 유명한 스크루지 민호가 다스리는 천나라가 있다. 천나라에는 N 개의 도시들이 있는데 각각의 도시들 사이에는 양방향 도로로 이어져 있다. 민호는 도시를 세울 때 최소한의 비용만을 www.acmicpc.net 아이디어를 생각해내는데 꽤나 걸렸던 문제입니다. 포인트는 현재 노드로부터 도달할 수 있는 리프 노드까지의 경로 길이 중에 홀수 길이가 있는지를 알아야합니다. 현재 노드로부터 홀수 경로 길이라면 현재 노드에 경찰서를 세워주면 됩니다. 호 만약, 길이가 짝수라면 자식 노드에 경찰서가 이미 세워져 있으므로 세울 필요가 없기 때문입니다. import sys, heapq from collections i.. 2023. 3. 16.
[백준] 연산자 끼워넣기 (3) https://www.acmicpc.net/problem/15659 15659번: 연산자 끼워넣기 (3) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 연산자 우선순위를 다루는 문제입니다. 비슷한 문제를 풀어본 경험이 있어서 쉽게 풀이할 수 있었습니다. 숫자들의 순서는 정해져있으므로 연산자들의 순서를 정해준 다음 수식을 만들어주어 계산을 해주면 됩니다. 수식 계산의 포인트는 1. 후위 연산으로 바꾸기 2. 후위 연산식 계산하기 입니다. 후위 연산식으로 바꾸는 방법은 숫자를 만나면 바로.. 2023. 3. 15.
[백준] 거의 최단경로 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라와 BFS를 통해 풀이하였습니다. 이 문제의 포인트는 최단 경로를 구성하는 간선들을 지워줘야합니다. 먼저, 다익스트라를 통해서 각 정점까지의 최단 경로의 길이를 구해줍니다. 그 다음으로는 역방향 그래프를 BFS로 탐색하면서 최단 경로를 구성하는 간선들을 지워주면 됩니다. 다익스트라를 통해 dist 배열에는 각 정점까지의 최단 경로의 길이가 저장 되어 있습니다.. 2023. 3. 14.
[백준] 양 구출 작전 https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 위상정렬 문제입니다. 단방향 그래프이면서 1번 섬으로 가는 경로가 각 섬에서 유일하므로 싸이클이 없음을 알 수 있으므로 위상정렬이 가능합니다. 위상정렬을 통하여 각 섬에 도달할 수 있는 양의 수가 양수이면 다음 노드로 양을 이주시키면 됩니다. import sys from collections import defaultdict, deque sys.stdin = open("input.. 2023. 3. 14.

티스토리툴바