21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 문제 준형이는 내일 친구들을 만나기로 했다. 준형이와 친구들은 서로 다른 도시에 살고 있다. 도시를 연결하는 도로는 일방 통행만 있어서 도시 $A_{i}$에서 도시 $B_{i}$로 가는 시간과 도시 $B_{i}$에서 도시 $A_{i}$로 가는 시간이 다를 수 있다. 준형이와 친구들은 아래 조건을 만족하는 도시 $X$를 선택하여 거기서 만나려고 한다. 왕복시간은 자신이 살고 있는 도시에서 도시 $X$로 이동하는 시간과 도시 $X$에서 다시 자신이 살고 있는 도시로 이동하는 시간을 합한 것이다. 준형이와 친구들이 도..
그래프이론
11909번: 배열 탈출 상수는 2차원 배열 A[1..n][1..n] (n≥2, n은 자연수)을 가지고 있습니다. 이 배열의 각 원소는 1 이상 222 이하의 정수입니다. 배열을 가지고 놀던 상수를 본 승현이는, 질투심이 불타올라 상수를 A[1][1] www.acmicpc.net 문제 상수는 2차원 배열 A[1..n][1..n] (n≥2, n은 자연수)을 가지고 있습니다. 이 배열의 각 원소는 1 이상 222 이하의 정수입니다. 배열을 가지고 놀던 상수를 본 승현이는, 질투심이 불타올라 상수를 A[1][1]에 가둬 버렸습니다! 최소한의 양심이 있던 승현이는 A[n][n]에 출구를 만들어 놓고 이 사실을 상수에게 알려줬습니다. [그림 1] n=4라면 상수는 A[1,1]에 있고, 출구는 A[4][4]에 있습..
21937번: 작업 민상이가 작업할 개수 $N$와 작업 순서 정보의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째줄부터 $M + 1$ 줄까지 작업 $A_i$와 작업 $B_i$가 공백으로 구분되어 주어진다. 이때 두 값의 의미는 작 www.acmicpc.net 문제 민상이는 자신이 해야할 작업 $N$개를 아래와 같이 작업 순서도로 그려보았다. 위 그림에서 5번 작업을 하기 위해 제일 먼저 2번 작업을 끝내야 하고 그 다음으로 4번 작업을 끝내야 5번 작업을 할 수 있다. 3번 작업은 먼저 해야하는 작업이 없으므로 3번 작업을 바로 시작 할 수 있다. 작업 순서를 정할때 위배되는 작업 순서는 없다. 예를 들어, A 작업을 하려면 B 작업을 먼저 해야하고, B 작업을 해야하기 전에 A 작업을 해야하는 상..
17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net 문제 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문자가 U인 경우에는 (r-1, c)로 이동해야 한다. R인 경우에는 (r, c+1)로 이동해야 한다. D인 경우에는 (r+1, c)로 이동해야 한다. L인 경우에는 (r, c-1)로 이동해야 한다. 미로에서 탈출 가능한 칸의 수를 계산해보자. ..
18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net 문제 NxN 크기 체스판의 특정한 위치에 하나의 나이트가 존재한다. 이때 M개의 상대편 말들의 위치 값이 주어졌을 때, 각 상대편 말을 잡기 위한 나이트의 최소 이동 수를 계산하는 프로그램을 작성하시오. 나이트는 일반적인 체스(Chess)에서와 동일하게 이동할 수 있다. 현재 나이트의 위치를 (X,Y)라고 할 때, 나이트는 다음의 8가지의 위치 중에서 하나의 위치로 이동한다. (X-2,Y-1), (X-2,Y+1), (X-1,Y..
