승형님의 블로그

https://www.acmicpc.net/problem/14554 14554번: The Other Way 첫째 줄에는 $N$, $M$, $S$, $E$가 하나의 공백으로 구분되어 들어온다. ($2 \le N \le 100000$, $N-1 \le M \le 300000$, $1 \le S, E \le N$, $S \neq E$) 그 후 $M$개의 줄에는 $A$, $B$, $C$가 하나의 공백으로 구분 되어 들어 www.acmicpc.net 요약 정점 S에서 출발하여 E에 도달하는 서로 다른 최단경로의 개수를 구한다. 1. 정점 S에서 E로 가는 최단경로는 다익스트라를 통해 구할 수 있다. 2. 서로 다른 최단경로의 개수를 구하기 위해서는 다익스트라로 최단거리를 찾는 과정에서 정확히 어떤 경로로 이동하였..

https://www.acmicpc.net/problem/14611 14611번: 월요병 첫 번째 줄에는 지도의 행의 수 N, 열의 수 M이 공백을 사이로 주어진다. (2 ≤ N, M ≤ 300) 다음 N 줄에는 각각 M 개 정수가 주어진다. -2는 벽이 있음을 의미하고, -1은 벽을 세울 수 없는 장소를 의미 www.acmicpc.net 요약 (1,1) 지점에서 (M,N) 지점으로 이어지는 길이 없게끔 벽을 세운다. 1. 미리 정해진 지도의 상태가 주어진다. 이때, 벽이 이미 존재하는 장소, 비용을 지불하고 벽을 세울 수 있는 장소, 벽을 세울 수 있는 장소, 3가지로 분류된다. 2. (1,1) 지점에서 (M,N) 지점으로 이어지는 길이 없게끔 벽을 세우는 아이디어를 떠올려보자. 다음과 같은 좌표 평면..

https://www.acmicpc.net/problem/17833 17833번: 홍익대학교 지하캠퍼스 홍익대학교 서울 캠퍼스의 건물들은 정문부터 후문까지 연결되어 있지만 건물마다 연결되어 있는 층이 제각각이다. 예를 들어 정문인 R동의 3층으로 나오면 K동의 1층이 있고, L동의 8층으로 나 www.acmicpc.net 요약 지하 R층에서 지하 D층으로 이어지는 캠퍼스 모델을 설계한다. 1. 시작 지점 지하 R층과 도착지점 지하 D층이 주어지고, 사용할 수 있는 건물 모델들이 주어진다. 이때, 모델이 최종적으로 위치한 범위가 지하 1층부터 지하 N층을 만족한다면 자유롭게 건물을 배치할 수 있다. 2. 모델을 제작하는데 T의 시간이 걸리고, 건물을 좌우로 반전시켜 배치할 수 있으므로, 가중치가 T인 양방..

https://www.acmicpc.net/problem/20046 20046번: Road Reconstruction 입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 www.acmicpc.net 요약 (1,1) 지점에서 (N,M) 지점으로 이어지는 경로를 만든다. 1. 미리 정해진 도시의 상태가 주어진다. 이때, 도로가 이미 존재하는 장소, 도로를 건설할 수 있는 장소, 도로를 건설할 수 없는 장소 3가지로 분류된다. 2. 도로가 이미 존재하는 장소는 비용이 0, 도로를 건설할 수 있는 장소는 가중치가 존재, 도로를 건설할 수 없는 ..

https://www.acmicpc.net/problem/2423 2423번: 전구를 켜라 첫째 줄에 문제의 정답을 출력한다. 전구에 불을 켜는 것이 가능하면, 몇 개의 칸을 돌려야 하는지를 출력하고, 불가능할때는 "NO SOLUTION"을 따옴표 없이 출력한다. www.acmicpc.net 요약 (0,0) 지점에서 (M,N) 지점으로 이어지는 회로를 만든다. 1. 미리 정해진 회로의 상태가 주어진다. 이때, 회로는 '/' 방향과 '\' 방향인 두 종류의 선으로 구성된다. 2. 정해진 방향의 회로를 따라 이동할 수도 있고, 이를 90도 회전시켜 방향을 돌린 뒤, 이동할 수 있다. 이때, 정해진 방향의 회로를 따라 이동할 때의 비용을 0, 방향을 회전시킨 뒤 이동하는 비용을 1로 하는 가중치 그래프를 떠올..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 요약 (1,1) 지점에서 (N,N) 지점으로 이어지는 미로를 만든다. 1. 미리 정해진 방의 상태가 주어진다. 이때, 흰 방은 조작 없이 지나갈 수 있고, 검은 방은 1회의 조작 후 지나갈 수 있다. 2. 인접한 흰 방으로의 이동은 비용이 0, 인접한 검은 방으로의 이동은 비용이 1인 그래프로 바꾸어 다익스트라로 풀이할 수 있다. 3. 다익스트라의 시간 복잡도는 $O\left ( \left| E\..