CEO

문제 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 문제 풀이 초기에 6면이 0의 값을 가지는 주사위를 동, 서, 북, 남으로 지도를 탐색할 경우 현재 좌표의 지도 값이 0이 아니면 주사위 바닥에 값을 복사하고, 현재 좌표 지도 값이 0인 경우 주사위 바닥의 수를 지도에 복사한다. 이때 명령에 따라 주사위를 움직일 때, 주사위 윗면의 값을 출력하는 문제이다. 주사위는 동, 서, 북, 남 각 방향에 따라 그림과 같이 변화한다. 동, 서인 경우에는..

문제 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 NxN 지도가 주어지고 각각의 칸에 높이가 주어진다. 이 지도에서 지나갈 수 있는 길이 몇 개 인지 찾아 반환하는 문제이다. 여기서 길은 지도의 하나의 행 또는 열을 의미한다. 길을 지나갈 때 높이가 다른 경우 경사로를 설치하여 지나갈 수 있게 만들 수 있다. 단 경사로의 길이만큼 길이가 확보되지 않거나, 경사로를 설치할 수 없는 영역 또는 높이의 차가 2 이상이라면 설치할 수 없다. 예제 입력 1의 경우 위의 그림과 같이 3개의 길을 지나갈 수 있다. 나머지 경우들은 ..

문제 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 풀이 NxN 정사각 보드가 있을 때, 초기의 뱀의 길이는 1이고 뱀은 처음에 오른쪽을 향한다. 이때 뱀은 사과를 먹게 되면 몸의 길이가 1 증가하고, 아닌 경우는 길이가 그대로 유지되고 이동한다. 또한 특정 시간 초 후에 전환하는 방향 'L', 'D'가 주어지는데 L인 경우 왼쪽, D인 경우 오른쪽으로 90도 회전한다. 이와 같은 조건에 따라 뱀 게임을 몇 초 동안 수행할 수 있는지 반환하여야 한다. 문제는 BFS를 통해 다음과 같이 탐색하면 된다. 뱀은 오..

문제 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 문제 풀이 N개의 약이 담긴 병이 주어질 때, 첫째 날에는 약을 꺼내서 반 조각으로 나눈 후 반은 먹고 반은 다른 병에 넣는다. 그다음 날에는 약을 꺼내서 반 조각이면 먹고, 반 조각이 아니라면 반을 쪼개서 먹은 후 남은 것은 다른 병에 넣는다. 한 조각을 꺼낸날에는 W, 반 조각을 꺼낸 날에는 H일 때 2N일 후에 서로 다른 문자열의 개수를 반환하는 문제이다. 이는 DFS를 통해 반 조각이 남아있는 경우를 반영하여 호출하면 쉽게 해결할 수 있다. 코드 from sys i..

연구소 시리즈 연구소 연구소 2 연구소 3 문제 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 문제 풀이 앞서 다룬 연구소 2 문제에서 조건이 조금 달라진 문제이다. 연구소 2에서는 바이러스를 설치하고, 바이러스가 설치가능한 위치이지만 설치되어있지 않을 경우 해당 영역에도 바이러스가 전파 가능하다. 하지만 이 문제에서는 바이러스가 설치 가능한 위치에 모두 설치되어 있고, `활성화`, `비활성화` 상태로 나뉘게 된다. 따라서 이미 바이러스가 설치된 곳이므로 전파가 불가능하여 `바이러스가 있는 위치를 제외시켜야 한다는 차..

연구소 시리즈 연구소 연구소 2 연구소 3 문제 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이�� www.acmicpc.net 문제 풀이 연구소에 바이러스 설치 가능한 위치가 있고, 설치 가능한 바이러스 수가 M개다. 바이러스는 하루마다 상, 하, 좌, 우로 바이러스를 전파시킨다. 이때 어떤 위치에서 바이러스 M개를 설치하여, 최소 날짜로 바이러스를 모두 전파시킬 수 있는 지를 찾아 반환하면 된다. 연구실 내에 벽을 제외한 모든 구간에 바이러스 전파가 불가능한 경우 -1을 반환한다. 앞서 다룬 연구소에서는 DFS를 사용하여 직접 조합을 구하였지만..

문제 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 문제 풀이 한 영역에 양과 늑대가 있을 때, 양의 수가 늑대보다 많다면 양만 남게 된다. 이와 달리 양의 수가 늑대와 같거나 늑대보다 적게 된다면, 양은 모두 잡아먹히고 늑대만 남게 된다. 이때, 각 영역에 양과 늑대의 수를 구하여 반환하는 문제이다. 문제는 앞서 다룬 단지번호붙이기와 같은 로직으로 풀되, 각 영역의 양의 수와 늑대의 수에 따라 BFS 호출 후에 반환되는 값을 달리하면 된다. 코드 from sys import stdin from..

문제 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있�� www.acmicpc.net 문제 풀이 문제에서 원숭이는 K번 동안, 나이트의 이동과 같이 8 방향으로 이동할 수 있으며 그 이후에는 상, 하, 좌, 우 한칸씩 움직이게 된다. 이때, 최소의 횟수로 우측 하단 아래의 좌표로 도착하는 경우를 반환하는 문제이다. 이는 벽을 K번 부술 수 있는 벽 부수고 이동하기 2와 유사한 로직으로 풀면 된다. BFS를 통해, K가 있다면 말, 원숭이 처럼 이동가능한 모든 경우의 수를 큐에 추가한다. K가 없다면, 원숭이 처럼 이동가능..