코딩하는 해맑은 거북이

해당 글은 백준 1238번 '파티' 문제를 다룬다.문제https://www.acmicpc.net/problem/1238 1238번: 파티첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어www.acmicpc.net 설명해당 문제는 최단 경로를 구하는 알고리즘 중 다익스트라를 활용하면 된다. x까지 가는 최단 경로와 x에서 집으로 돌아오는 최단 경로를 2번의 다익스트라로 구할 수 있다. 코드import heapq import sys input = sys.stdin.readline INF = int(1e9) n, m, x = map..

해당 글은 백준 1141번 문제 '접두사'을 다룬다. 문제 https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 설명 해당 문제는 문자열을 다루는 문제로, 입력받은 단어들을 길이순으로 정렬하여 비교하였다. 접두사가 아닌 부분집합의 최대크기를 구하므로, 2중 for문으로 현재 단어가 다음 단어의 접두사라면 결과에 포함시키지 않으면 된다. 코드 n = int(input()) words = [] ..

해당 글은 백준 1240번 문제 '노드사이의 거리'을 다룬다. 문제 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 설명 해당 문제는 그래프로 모든 노드에 대한 거리값을 저장해두고, 두 노드 사이의 거리를 구할 때 BFS 를 사용하여 해결할 수 있다. 코드 from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().spl..

해당 글은 백준 2589번 문제 '보물섬'을 다룬다.문제https://www.acmicpc.net/problem/2589 2589번: 보물섬보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서www.acmicpc.net 설명해당 문제는 L의 위치 각각에서 BFS로 탐색한 후, 가장 먼 지점을 반환해주면 된다. 여기서 모든 L의 위치에서 BFS를 하면, 시간초과가 발생하였고 시간을 줄이기 위해 현재 'L'의 위치에서 상하로 L이 존재하거나, 좌우로 L이 존재하면 보물이 있는 위치가 아니므로 해당 경우에는 BFS를 하지않으면 해결할 수 있다. 코드import copy ..

해당 글은 백준 1717번 문제 '집합의 표현'을 다룬다. 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 설명 해당 문제는 그래프의 유니온 파인드 해결법으로 풀 수 있다. 1. N+1 개의 노드에 대해 자기자신으로 부모를 초기화 해준다. 2. union시 더 작은 값으로 부모를 지정해준다. 3. 같은 집합인지 판별하기 위해, 부모를 찾아 비교해준다. 또한, 주의할 점은 재귀한계를 설정해주지 않았더니 ..

해당 글은 백준 14502번 문제 '연구소'을 다룬다. 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 설명 해당 문제는 3개의 벽을 세울 수 있는 모든 경우의 수에 BFS를 하여 0의 갯수가 최대인 값을 구하면 된다. 3개의 벽을 세울 수 있는 경우는 조합을 통해 구하고, 새로운 배열에 대해서는 deepcopy 함수를 사용하였다. 코드 from itertools import combinations from collections import deque..