본문 바로가기

전체 글91

백준(BOJ) 18224 미로에 갇힌 건우(Python) BFS 문제. 일반적인 BFS 문제와는 달리 이미 한 번 방문한 노드여도 지금 상태가 낮인지 밤인지, 몇 번 움직인 상태인지에 따라 최단 거리가 달라지는 문제이다. 따라서 일반적인 visited가 아닌, 각 노드에 낮밤과 움직인 횟수를 더 고려하는 visited를 사용해야 BFS를 통해 최단 거리를 구할 수 있었다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionlimit(100000000) n,m=map(int,input().split()) L=[list(map(int,input().split.. 2022. 7. 11.
1주차 정리 블로그를 시작한 지 일주일 정도 된 것 같다. 백준을 제대로 시작한 게 지난 주 월요일이니까 대충 어제까지 1주차라고 치자. 백준 제대로 시작할 때 168포인트가 남았는데, 지금은 63포인트밖에 안 남았다. 문제 난이도에 따라서 포인트가 올라서 문제 당 4~5포인트씩 주는 골드 2 ~ 플래 4 정도의 문제를 여럿 풀어서 포인트가 빠르게 올라가는 것 같다. 문제를 풀면서 느끼는 거는, 확실히 백준 티어가 실력을 증명할 수 없다는 것이다. 골드 문제를 100개 푸는 것보다 플래티넘 문제 20개 푸는 게 지금 내 상황에서는 티어가 더 많이 오르긴 하는데, 실력을 올리는 데에는 전자가 더 효과적이라는 것이다. 지난 한 주 동안 30문제 정도 풀었는데, 일단 문제를 이해하거나 푸는 속도가 점점 빨라지는 것이 느껴.. 2022. 7. 11.
백준(BOJ) 17404 RGB거리 2(Python) 2차원 DP 문제. 처음 집에 색을 칠하는 경우 총 3개를 각각 나눠서 DP를 돌렸다. 그 이유는, 2번째부터 n-1번째 집까지는 i번째 집을 칠할 때 i-1번째와 다르게만 칠하면 되지만 n번째 집을 칠할 때에는 1번째 집을 칠한 색이 영향을 끼치기 때문이다. 그 외에는 크게 어려운 부분이 없는 DP 문제였다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionlimit(100000000) n=int(input()) L=[] for i in range(n): L.append(list(map(int,.. 2022. 7. 11.
백준(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.

티스토리툴바