www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 아이디어: 플로이드 와샬 알고리즘을 구현하여 쉽게 풀 수 있는 문제인 건 알겠는데, 왜 시작도시와 도착도시가 같은 경우에는 경유해서 갈 수 있어도 무조건 0을 출력해야 하는 건 지 이해가 안간다. 내가 문제 이해를 잘 못하는 건가. 예를 들어 문제 예시에 1 3 3이 있고 3 1 8 도 있는데 그렇다면 1 3 3 버스를 타고 1번에서 3번으로 이동하고, 다시 3 1 8버스를 타고 3번에서 1번으로 이동하여 결국..
분류 전체보기
www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어: 플로이드 와샬 알고리즘을 이용하여 경로를 찾고, 경로가 있는 경우와 없는 경우만 구별해서 출력하면 된다. graph로 입력받은 배열에서 경로가 존재하지 않는 경우(0인 경우)에 0 대신 INF값을 넣었고, 이를 이용하여 플로이드 와셜 알고리즘으로 탐색하였다. 그 후, graph[i][j]==INF면 0을, 아니면 1을 출력하였다. import sys N = int(sys.stdin.readline()) graph = [[] for _ in r..
www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 아이디어: 플로이드-와샬 알고리즘을 이용하여 푸는 문제이다. 플로이드-와샬 알고리즘은 모든 정점 쌍에 대한 최단경로를 구할 수 있는 알고리즘으로, dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]) 를 이용하여 구현하면 되고 시간복잡도는 O(V^3)이다. 이 문제에서는 친구 관계를 입력받으면서 dist[A][B]=dist[B][A]=1을..
www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 아이디어: 벨만-포드 알고리즘을 구현하여 푸는 문제는 맞는데, 조건을 따질 게 좀 있어서 헤맸다. 1. N, M, W를 TC for 문 안에서 받아야 하는데 바보처럼 밖에서 받음. 2. 도로는 양방향이고, 웜홀은 단방향임.. 3. 음수 사이클이 어디서 시작하는 지는 상관없이 존재 유무만 판단하는 것이므로, 1에서만 탐색하면 안되고 방문하지 않은 모든 정점을 탐색해야 함. import sys TC =..
www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 아이디어: 벨만-포드 알고리즘을 이용하여 최단경로를 구해야한다. 다익스트라 알고리즘은 간선의 가중치가 음수인 경우에는 사용하지 못하기 때문이다. 벨만-포드 알고리즘의 시간복잡도는 O(VE)이다. 벨만 - 포드 알고리즘은 존재하는 모든 간선을 V-1번 돌아보면서 이 간선을 통할 수도 있는 최단경로들의 거리를 갱신하는 것이다. 왜 V-1번 이냐면 최단 경..
www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 아이디어: 문제 이름 그대로 최대 힙을 구현하면 된다. 그런데 파이썬에서 제공하는 heapq 모듈은 최소힙이므로, 최대힙을 구현하려면 튜플을 이용하여 - 추가하는 첫번째 원소가 우선순위가 되고 이걸 기준으로 최소힙으로 정렬되므로 - 구현해야 한다. 출력할 때는 [1]번 원소를 출력하면 된다. #11279번 최대 힙 import sys, heapq N = int(sys.stdin.readlin..
www.acmicpc.net/problem/20046 20046번: Road Reconstruction 입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 www.acmicpc.net 아이디어: 차량은 가로나 세로방향으로만 움직이므로 현재 위치에 인접한 정점은 상하좌우 좌표라고 할 수 있다. 그럼 인접한 정점을 이동하면서 최소 비용을 업데이트하면 되지 않을까? 했는데 해결됐다!ㅎㅎ 그냥 다익스트라 알고리즘과 똑같이 구현하면 된다. import sys, heapq m, n = map(int, sys.stdin.readline().split..
www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 아이디어: 앞선 다익스트라 구현 문제와 똑같은 문제이다. 이것도 기본문제니까 다시 풀어보자. import sys, heapq N = int(sys.stdin.readline()) M = int(sys.stdin.readline()) graph = [[] for _ in range(N+1)] for _ in range(M): s, e, w = map(int, sys.stdin.r..
www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 아이디어: 다익스트라 알고리즘을 활용하여 푸는 기본적인 문제이다. 다익스트라 알고리즘은 최단경로를 구하는데 사용하는 알고리즘이다. 시작정점으로부터 거리가 가장 작은 정점부터 방문하여 최소경로를 계속 갱신하는 방식이다. 이론은 이해가 가지만 구현하는 게 아직 익숙하지 않아서 어려웠다. 힙을 사용하여 시작정점으로부터의 거리를 저장하는 방식과, 이미 방문한 노드를 거르는 조건에 주의하자. ..
www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 아이디어: 처음에는 저번에 다른 회의실 문제를 풀었을 때처럼 종료시간을 기준으로 정렬하였다. 근데 그렇게 풀다보니 풀리지 않는 경우가 발생하였다. 4 1 3 2 4 4 8 3 9 이와 같은 경우에는 4 8 강의를 2 4 강의실에 배정해야 하는데 1 3 강의실에 배정이 되어서 오답이 나온다. 그래서 질문을 찾아보니.. 이 문제는 시작시간을 기준으로 정렬을 해서 풀어야 하는 문제였다. heapq를 사용하고, 끝나는 시간을 저장하는 배열end도 heapq를 사용하..
