본문 바로가기

백준80

백준(BOJ) 2887 행성 터널(Python) 최소 신장 트리 문제. 입력받은 행성을 각각 x, y, z좌표 기준으로 오름차순 정렬한 리스트를 3개 만들고, 각 리스트 별로 i번째 행성와 i+1번째 행성을 잇는 터널의 연결 비용을 계산해 전체 간선 리스트에 저장했다. 그 후 전체 간선 리스트에서 크루스칼을 돌렸다. 좌표 별로 정렬한 이유는, 결국 행성과 행성 간의 터널의 연결 비용은 행성의 세 좌표 중 하나에만 의존하기 때문이다. 행성 간의 모든 간선을 연결하면 당연히 시간 초과가 터질 것이기에, 간선의 수를 위와 같이 줄이면 총 3*(n-1)개의 간선이 만들어진다. 위와 같이 간선을 만들어도 상관 없는 이유는, 예를 들어 x1, x2, x3 순으로 리스트에 들어있을 때 (x1과 x2를 잇는 간선의 가중치)+(x2과 x3를 잇는 간선의 가중치)=(x.. 2022. 7. 11.
백준(BOJ) 1185 유럽여행(Python) 최소 신장 트리 문제. 크루스칼 알고리즘으로 해결했다. 입력받은 간선의 가중치를 수정해서 문제를 해결했는데, 가중치를 (원래 가중치)*2+(양 노드의 방문 비용)으로 수정했다. 모든 길을 제거한 상태가 트리이므로, 어떤 한 노드에서 출발해 다른 모든 노드를 방문하고 다시 원래 노드로 돌아오기 위해서는 모든 간선을 2번씩 거쳐야 하기 때문이다. 그 과정에서 양 노드의 방문 비용도 발생하기 때문에 처음부터 간선의 가중치를 그 간선을 왕복할 때의 비용으로 수정해서 문제를 풀 수 있었다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readlin.. 2022. 7. 11.
백준(BOJ) 1197 최소 스패닝 트리(Python) 간단한 최소 신장 트리 문제. 별다른 설명을 할 게 없다. 크루스칼, 프림 등등 최소 신장 트리 알고리즘 중 하나 선택해서 적용하면 바로 풀린다. 나는 크루스칼을 사용했다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionlimit(100000000) v,e=map(int,input().split()) L=[] cycle=[i for i in range(v+1)] ans=0 n=0 for i in range(e): a,b,c=map(int,input().split()) heapq.heappush(.. 2022. 7. 11.
백준(BOJ) 1113 수영장 만들기(Python) BFS 문제. 가장 먼저 물을 채울 시작점을 구해야한다고 생각했다. 물을 채울 수 있다는 근거는, 칸의 상하좌우 중 현재 칸의 높이보다 높은 칸이 존재하는 것이라고 생각했다. 그렇게 칸을 정하고 나면 상하좌우 중 가장 높은 높이부터 가장 낮은 높이까지 물을 채워본다. 편의상 물의 높이를 w라 하겠다. w보다 칸의 높이가 더 낮다면 queue에 칸의 좌표를 push하는 방식으로 BFS를 진행했다. 만약 BFS를 진행하다 리스트 범위를 벗어나는 좌표가 나타나면 이는 물이 넘치는 것이므로 BFS를 중단한다. 그렇지 않고 끝났다면 현재 w는 그 칸에서 시작해 채울 수 있는 가장 높은 물의 높이일 것이므로, BFS를 하며 계산한 수영장의 부피를 ans에 더한다. 만약 물을 채우는 데에 성공했다면 모든 칸의 높이를.. 2022. 7. 11.
백준(BOJ) 1724 그림판(Python) BFS로 풀 수 있었던 문제. 일반적인 BFS 문제와는 달리 벽을 생성해야 하는 문제였다. 컴실1 maze project에서 이와 비슷한 유형의 자료구조를 구현해봤기 때문에 쉽게 풀 수 있었다. 2차원 리스트의 각 칸을 하나의 픽셀로 생각하고, 그 픽셀의 상, 하, 좌, 우 방향으로 이동할 수 있는지를 체크해줬다. 처음에는 모두 이동할 수 있도록 초기화하고, 가장자리 픽셀에서 리스트 밖으로는 벗어나지 못하도록 한 뒤 선분을 입력받는다. 입력받은 선분이 리스트의 가장자리에 위치한다면 pass하고, 그렇지 않은 경우 두 점의 x좌표가 동일하다면 x좌표를 기준으로 변화하는 y좌표에 대해 해당하는 선분의 위 픽셀은 아래로 이동할 수 없고, 아래 픽셀은 위로 이동할 수 없도록 설정한다. y좌표는 x좌표와 마찬가지.. 2022. 7. 10.
백준(BOJ) 3111 검열(Python) 문자열 테크닉으로 해결할 수 있는 문제였다. 앞에서부터 stack(L1)에 문자를 하나씩 넣다가 L1의 마지막 index부터 len(A)만큼 문자열을 체크해서 그 문자열이 A와 같으면 len(A)개 만큼 pop, 그 다음에는 새 stack(L2)에 뒤에서부터 문자를 하나씩 넣다가 L2의 마지막 index부터 len(A)만큼 문자열을 체크해서 그 문자열이 reversed(A)와 같으면 len(A)개 만큼 pop한다. 위의 모든 작업이 끝나면 L2에서 pop한 문자를 L1에 push하면서 마지막 index부터 len(A)만큼 문자열을 체크해서 그 문자열이 A와 같으면 len(A)개 만큼 pop해준다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collecti.. 2022. 7. 10.

티스토리툴바