[백준] 20007번: 떡 돌리기

https://www.acmicpc.net/problem/20007 20007번: 떡 돌리기 첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N) 두번째 줄부터 M+1번째 줄까지 A와 B 그리고 A집과 B집 사이의 도로의 길이 C가 주 www.acmicpc.net 1. 문제 조건 1) $N$ 개의 집과 $M$ 개의 양방향 도로가 주어진다. 2) 한 번에 떡 한 개만 가지고 모든 집을 방문해야 한다. 즉 어떤 집에 도착하면 다시 집에 가야한다. 3) 거리가 가까운 집부터 방문한다. 4) 하루에 최대 $X$ 만큼만 이동할 수 있다. 5) 하루 최대 이동 거리 안에 $i$번째 집으로 왕복이 ..

[백준] 22865번: 가장 먼 곳

https://www.acmicpc.net/problem/22865 22865번: 가장 먼 곳 $N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들의 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할 www.acmicpc.net 1. 문제 조건 1) $N$ 개의 땅이 주어진다. 2) 친구 A, B, C 는 $N$ 개의 땅 중 하나에 살고 있다. 3) 양방향 간선 $M$ 개와 각각의 길이가 주어진다. 4) 친구 A, B, C 에 대해 각각 가장 가까운 땅을 구하는데, 그 중 가장 먼 땅의 번호를 출력한다. 2. 문제 풀이 다익스트라 알고리즘을 사용해서 풀 수 있다. 처음엔 이게 뭔 소린가 했는데, 별..

[백준] 12834번: 주간 미팅

https://www.acmicpc.net/problem/12834 12834번: 주간 미팅 첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000) 둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V) 셋째 줄에 팀원 N명의 www.acmicpc.net 1. 문제 조건 1) 팀원 수 $N$, 장소 수 $V$, 간선 수 $E$ 가 주어진다. 2) 2개의 목적지 $A$ 와 $B$ 가 주어진다. 3) 각 팀원의 집 위치가 주어진다. 4) $i$ 번째 팀원 집의 위치가 $H_{i}$ 라고 할 때, $d_{i}$ 는 ($H_{i}$ 와 $A$의 최단거리) + ($H_{i}$ 와 $B$의 최단..

[백준] 20046번: Road Reconstruction

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) $M \times N$ 크기의 격자가 주어진다. 2) 흰색 격자, 검은색 격자, X 격자가 있다. 3) 흰색 격자는 도로가 없는 구역, 검은색 격자는 도로가 있는 구역, X 격자는 도로 설치가 불가한 구역이다. 4) 도로를 새로 설치하는 비용은 1 또는 2이다. 5) 흰색 격자는 0, 검은색 격자는 1 또는 2, X 격자..

[백준] 14497번: 주난의 난(難)

https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 1. 문제 조건 1) $N \times M$ 크기의 교실이 주어진다. 2) 교실에는 빈 공간과 친구, 시작점과 도착점이 주어진다. 3) 빈 공간은 0, 친구는 1, 시작점은 *, 도착점은 # 으로 표시된다. 4) 한 번 점프할 때마다 시작점이 포함된 0을 둘러싼 1을 모두 0으로 바꾼다. 5) 도착점을 0으로 바꿀 수 있을 때까지 점프한 횟수의 최솟값을 출력한다. 2. 문제 풀이 다익스..

[백준] 18223번: 민준이와 마산 그리고 건우

https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 1. 문제 조건 1) $V$ 개의 노드와 $E$ 개의 간선이 주어진다. 2) 간선은 양방향 통행이 가능하며, 1 이상의 자연수다. 3) 출발지는 1번, 도착지는 $V$ 번이며, 건우는 $P$ 번 노드에 있다. 4) 건우가 있는 노드를 경유해서 도착지로 갈 때, 경유하지 않고 갈 때보다 최단 거리가 길어지지 않는다면 "SAVE HIM" 을 출력한다..

[백준] 13424번: 비밀 모임

https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 1. 문제 조건 1) $N$ 개의 방과 $M$ 개의 비밀 통로가 주어진다. 2) 친구 $K$ 명이 있는데, 각 찬구들이 있는 방 번호가 주어진다. 3) 통로는 양방향 통행이 가능하며, 길이는 자연수다. 4) 모든 친구들의 이동 거리의 합이 최소가 되는 지점의 번호를 출력한다. 5) 만약 거리의 합이 최소가 되는 지점이 여러 개라면, 가장 작은 번호를 출력한다. 2. 문제 풀이 다익스트라 알고리즘을..

[백준] 2665번: 미로만들기

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 1. 문제 조건 1) $N \times N$ 크기의 방이 주어진다. 2) 모두 검은 방과 흰 방으로 구성된다. 3) 검은 방은 0, 흰 방은 1로 주어진다. 4) 상하좌우 1칸씩 이동할 수 있다. 5) 흰 방은 자유롭게 이동할 수 있지만, 검은 방은 지나갈 수 없다. 6) 검은 방을 흰 방으로 바꿀 수 있다. 7) 시작점은 (0, 0) 이고, 도착점은 ($N-1$, $N-1$) 이다. 8) 시작점..

[백준] 4485번: 녹색 옷 입은 애가 젤다지?

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 1. 문제 조건 1) $N \times N$ 크기의 동굴이 주어진다. 2) 각 좌표에는 도둑 루피가 존재한다. 3) 도둑 루피가 있는 좌표에 가면, 그 값만큼 소지금이 줄어든다. 4) 시작점은 (0, 0) 이고, 도착점은 $(N-1, N-1)$ 이다. 5) 상하좌우 1칸씩 이동할 수 있다. 6) 도착점까지 이동했을 때, 잃어버린 루피의 최솟값을 출력한다. 2. 문제 풀이 다익스트..

[백준] 1261번: 알고스팟

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 1. 문제 조건 1) $N \times M$ 크기의 미로가 주어진다. 2) 미로는 빈 방 또는 벽으로 구성되어 있다. 3) 빈 방은 자유롭게 이동, 벽은 부숴야 이동할 수 있다. 4) 빈 방은 0으로, 벽은 1로 표시된다. 5) 상하좌우 1칸씩 이동이 가능하다. 6) 시작점은 (1, 1), 도착점은 ($N$, $M$) 이다. 7) 시작점에서 도착점까지 이동할 때 부숴야 하는 ..