커리까지

문제 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게임이다. '나무 탈출' 은 N개의 정점이 있는 트리 모양으로 생긴 게임판과 몇 개의 게임말로 이루어진다. 트리의 각 정점에는 1번부터 N번까지 번호가 붙어있다. 1번 정점은 '루트 노드' 라고 불리며, 이 루트 노드를 중심으로 정점 간에 부모-자식 관계가 만들어진다. 자식이 없는 노드는 '리프 노드' 라고 불린다. 이 게임은 두 사람이 번갈아 가면서 게임판에 놓여있는 게임말을 움직이는 게임이다. 처음에는 트리의 모든 리프 노드에 게임말이 하나씩 놓여있는 채..

문제 윌리암슨수액빨이딱따구리 세 식구가 정보섬에 올라왔다! 세 윌리암슨수액빨이딱따구리는 정보섬 2층 어딘가에 모여 앉아 쉬고 있었는데, 저 멀리 청국장과 스시와 맥앤치즈가 있는 것을 발견했다! 아빠는 청국장, 엄마는 스시, 아이는 맥앤치즈가 먹고 싶다. 그래서 이 셋은 현위치로부터 가장 가까운 음식을 먹으러 가기로 했다. 정보섬 2층은 An×m의 격자로 표현된다. 어떤 Ai,j가 0이면 빈 복도여서 지나갈 수 있고, 1이면 장애물로 막혀 지나갈 수 없다. 윌리암슨수액빨이딱따구리 식구는 2, 청국장은 3, 스시는 4, 맥앤치즈는 5이다. 윌리암슨수액빨이딱따구리는 단위 시간마다 한 칸, 상하좌우로 움직일 수 있다. 2, 3, 4, 5는 장애물이 아니므로 지나갈 수 있다. 격자 밖으로는 나갈 수 없으며 시작점..

문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 6 8 2 6 2 3 2 3 4 6 6 7 3 3 2 7 2 5 3 6 8 9 5 2 7 이제 위와 같은 지역에 많은 비가 내려서 높..

문제 NxN 크기 체스판의 특정한 위치에 하나의 나이트가 존재한다. 이때 M개의 상대편 말들의 위치 값이 주어졌을 때, 각 상대편 말을 잡기 위한 나이트의 최소 이동 수를 계산하는 프로그램을 작성하시오. 나이트는 일반적인 체스(Chess)에서와 동일하게 이동할 수 있다. 현재 나이트의 위치를 (X,Y)라고 할 때, 나이트는 다음의 8가지의 위치 중에서 하나의 위치로 이동한다. (X-2,Y-1), (X-2,Y+1), (X-1,Y-2), (X-1,Y+2), (X+1,Y-2), (X+1,Y+2), (X+2,Y-1), (X+2,Y+1) N=5일 때, 나이트가 (3,3)의 위치에 존재한다면 이동 가능한 위치는 다음과 같다. 나이트가 존재하는 위치는 K, 이동 가능한 위치는 노란색으로 표현하였다. 예를 들어 N=5..

문제 ‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다. ‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다. ‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다. ‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다. ‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다. ‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는..

문제 동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 �(N)번 돌 위에, 주미는 �(M)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 �,�(A, B) 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 �(A)나 �(B)만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 �(A)배나 �(B)배의 위치로 이동을 할 수 있다. 예를 들어 지금 동규가 7번 돌 위에 있고 스카이 콩콩의 힘이 8이면 그냥 점프를 해서 15번 돌에 ..

문제 양치기 꿍은 맨날 늑대가 나타났다고 마을 사람들을 속였지만 이젠 더이상 마을 사람들이 속지 않는다. 화가 난 꿍은 복수심에 불타 아예 늑대들을 양들이 있는 울타리안에 마구 집어넣어 양들을 잡아먹게 했다. 하지만 양들은 보통 양들이 아니다. 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다. 물론 그 외의 경우는 양이 전부 잡아먹히겠지만 말이다. 꿍은 워낙 똑똑했기 때문에 이들의 결과는 이미 알고있다. 만약 빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'라고 나타낸다면 여러분은 몇 마리의 양과 늑대가 살아남을지 계산할 수 있겠는가? 단, 울타리로 막히지 않은 영역에는 양..

문제 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다. 데스 나이트는 체스판 밖으로 벗어날 수 없다. 입력 첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다. 출력 첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 ..

문제 한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다. cdef ...f ..ef ..gh cdeh cdej ...f bT.. .T.e .Td. .Tfe bTfg bTfi .Tde a... abcd abc. abcd a... a.gh abc. 거리 : 6 6 6 8 8 10 6위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다. 입력 첫 줄에 정수 R(1..

문제 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라. 문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자. 입력 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다. 출력 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 예제 입력 1 15 15 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1..