16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS를 활용한 구현 문제. 풀이 코드 from collections import deque INF = int(1e9) # 무한(10억) # 맵의 크기 N 입력 n = int(input()) # 전체 모든 칸에 대한 정보 입력 array = [] for i in range(n): array.append(list(map(int, input().split()))) # 아기 상어의 현재 크기 변수와 현재 위치 변수 now_size = 2 now_x, now_y ..
이것이코딩테스트다
3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상 정렬 문제다. 문제에서는 작년 순위와 상대적으로 순위가 바뀐 팀들의 목록이 주어졌을 때, 올해 순위를 만들 것을 요구한다. 즉, 정해진 우선순위에 맞게 전체 팀들의 순서를 나열해야 한다는 점에서 위상 정렬 알고리즘을 떠올릴 수 있어야 한다. 예를 들어 순위가 5 4 3 2 1 순으로 주어진다면 5 -> 4, 3, 2, 1 4 -> 3, 2, 1 3 -> 2, 1 2 -> 1 을 가리키도록 그래프를 만든다. (여기서 이렇게 그래프를 만들었으면 바로 풀..
2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 최소 신장 트리를 구하면 되는 문제이다. 하지만 이전 문제들보다 어려운 점이 있다면, 노드(행성)들 사이에 연결된 간선에 대한 정보가 주어져 있지 않다. 각 노드들의 좌표들만 주어져 있고, 두 노드의 좌표를 사용해 두 노드 간의 간선 비용을 구할 수 있다. 행성의 개수 N이 최대 10만개이므로 모든 노드의 거리를 구해서 크루스칼 알고리즘을 사용하려면 O(N(N+1) / 2)의 시간이 걸리고, 이는 무조건 시간 초과가 발생한다. 밑..
문제를 읽어보면, 가로등이 켜진 도로만을 이용해서, 모든 두 집이 서로 도달 가능해야 한다는 조건을 제시한다. 이 때, 최소한의 비용으로 모든 집을 연결해야 하므로, 전형적인 최소 신장 트리 문제라는 것을 확인할 수 있다. 전형적인 크루스칼 알고리즘 문제다. 내 풀이 코드 # 어두운 길 # 특정 노드가 속한 집합을 찾는 함수 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 노드가 속한 집합을 합치는 함수 def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) ..
이 문제는 도저히 어떻게 풀어야할지 감이 잡히지 않아서 풀지 못했다. 아이디어 부분에서 막힌 문제. 문제 자체는 쉽지만, 문제 조건을 보면 탑승구의 개수가 최대 10만개, 그리고 비행기의 개수가 최대 10만개라서 단순히 반복문을 통해 구현하면 무조건 시간초과가 뜨는 문제이다. 그래서 어떻게 해결해야할지 감을 잡지 못해 풀지 못했다. 풀이 이 문제는 서로소 집합 알고리즘을 사용해서 푸는 문제다. 각 탑승구를 서로 다른 집합으로 나타낸다고 해보자. 전체 탑승구가 4개일 때, 루트 0 1 2 3 4 탑승구 0 1 2 3 4 초기 상태에는 모두 루트 노드로 자기 자신을 가리키고 있다고 가정한다. 0번 탑승구는 존재하지 않지만, 문제 해결을 위해 0번 탑승구도 그려준다. 이 때, 비행기가 순서대로 들어오면 차례대..
문제에서 등장하는 여행지의 관계를 그래프로 그린다. 이 문제에서는 서로소 집합 알고리즘을 사용해서, 그래프 간의 연결성을 파악해 해결한다. "여행 계획"에 해당하는 모든 노드가 같은 집합에 속해 있다면, 가능한 여행 경로가 될 수 있다. 따라서 두 노드 사이에 도로가 존재하는 경우에는 union 연산을 통해 서로 연결된 두 노드를 같은 집합에 속하도록 만든다. 결과적으로는 여행 계획에 포함되는 모든 노드가 모두 같은 집합에 속하는지를 체크하여 출력하면 된다. 내 풀이 코드 # 여행 계획 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[..
다익스트라 알고리즘을 이용해 1번 노드 ~ 다른 모든 노드까지의 최단 거리를 구하면 나오는 distance 리스트를 통해 풀 수 있는 문제. 여기서는 각 노드 사이의 거리가 1이기 때문에 BFS를 이용해서도 풀 수 있지만, 다익스트라 알고리즘을 사용하면서 각 노드 사이의 거리를 1로 넣어주면 다익스트라 알고리즘으로도 풀 수 있다. 내 풀이 코드 # 숨바꼭질 import heapq, sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] # (도착노드, 거리)를 저장하기 위한 리스트 distance = [INF] * (n+1) # 최단거리를 저장하기 위한 리스트 ..
이 문제는 이차원 리스트가 주어졌을 때, (0,0) 위치에서 (N-1,N-1) 위치로 이동하는 최단 거리를 계산하는 문제다. N X N 크기의 맵이 주어졌을 때, 맵의 각 위치(칸)을 노드로 보고, 상하좌우로 모든 노드가 연결되어 있다고 생각하면 된다. dx, dy 리스트를 사용하는 방법 + 다익스트라 알고리즘 구현 방법을 알고 있다면 쉽게 풀 수 있는 문제. 내 풀이 코드 # 화성 탐사 import heapq, sys input = sys.stdin.readline INF = int(1e9) # 최단 거리 탐색 def dijkstra(): q = [] n = int(input()) # 맵 크기 graph = [list(map(int, input().split())) for _ in range(n)] #..
최단 거리 문제이다. 책 풀이는 플로이드-워셜 알고리즘을 활용해서 풀었으나, 나는 다익스트라 알고리즘 같은 느낌의 알고리즘을 사용해서 풀었다. 내 풀이 # 정확한 순위 import sys, heapq input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) # n은 학생 수, m은 두 학생의 성적을 비교한 횟수 graph = [[] for _ in range(n+1)] connected = [[False] * (n+1) for _ in range(n+1)] # connected[i][j] = i->j로 연결되어 있는지 여부를 저장 # 성적 비교 입력 for _ in range(m): a, b = map(int, input().s..
11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제. 플로이드-워셜 알고리즘의 시간복잡도는 O(V^3)인데, 도시 개수가 최대 100개이므로 시간 복잡도도 만족한다. 단, 이 문제에서는 추가된 조건들이 있다. 1. 시작도시와 도착도시가 연결된 노선은 하나가 아닐 수 있다. 2. 마지막에 최단 거리를 출력할 때, 갈 수 없는 경우에는 0을 출력한다. 1번 조건을 만족하기 위해, 이차원 리스트에 거리를 입력할 때, 입력받은 거리가 원래 입력되어 있는 거리보다..
