문제 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가 없다면, 원숭이 처럼 이동가능..
문제 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 문제 풀이 S가 주어질 때 S를 사칙연산(`*`, `+`, `-`, `/`)을 통해 T로 만드는 경우 사용한 연산자들을 출력하는 문제이다. 이 문제는 BFS를 통해 풀 수 있으며, `*`, `+`, `/`에 대해서만 경우의 수를 찾기 위해 가지를 뻣으면 된다. 왜냐하면 `-`의 경우 값이 빠지게 되므로 최소 연산 횟수를 벗어나기 때문이다. 또한, 연산의 아스키코드 순서의 우선순위를 보장하기 위해, 가지를 뻗어 나갈 때 `*`, `+`, `/` 순으로 ..
문제 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 풀이 그래프에 `R`, `G`, `B` 세 가지 색깔이 주어지는데, 적록색약의 경우 `G`를 구분할 수 없다. 이에, 그래프의 영역을 탐색하되, 색약이지 않는 사람이 구분하는 영역과 적록색약인 사람이 구분하는 영역을 출력하는 문제이다. 앞서 다룬 단지 번호 붙이기와 동일한 로직으로 풀면 된다. 다른 점은 한번 그래프를 탐색하고, `G`인 경우에는 `R`로 바꾸어 다시 한번 탐색하여야 한다. 또한, 단지의 수를 세는 것이 아닌 영역의 수를 센다는 ..
