개발 일지

문제 어른 상어가 마법사가 되었고, 파이어볼을 배웠다. 마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다. 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다. 7 0 1 6 2 5 4 3 마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다. 이동하는 중에..

문제 19237번: 어른 상어 (acmicpc.net) 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 풀이 1 상어가 매번 이동할 때 마다 "냄새 값"이 1씩 줄어드는데, 어렵게 생각할 필요 없이, 매 초마다 모든 냄새 값을 1씩 빼준 뒤 상어가 위치하는 곳에 냄새 값을 K로 갱신해주면 된다. while 문 안에 들어가는 로직만 잘 설계하면 생각보다 어렵지는 않은 문제이다. import heapq # 북,남,서,동 dRow = [-1,1,0,0] dCol = [0,..

문제 19238번: 스타트 택시 (acmicpc.net) 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 1 문제에는 명시되어 있지 않지만, 각 손님의 출발지점은 다르지만 도착지점은 같을 수 있다. 처음에는 각 손님에 대해서 거리를 구해 heapq에 넣었지만, 시간초과가 발생한다. 택시의 위치부터 보드 전체를 탐색하며 남아있는 손님을 탐색하면 시간초과가 발생하지 않는다. 여러 제한 조건들을 유의해서 풀이해야하는 문제이다. from collections import d..

문제 19236번: 청소년 상어 (acmicpc.net) 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 풀이 1 문제에서 상어가 물고기를 먹는 경우 중 번호의 합이 최대가 되는 경우를 구해야 하므로, 백트래킹으로 접근해야겠다는 판단이 가능하다. 또한 조건에서 물고기 번호는 유일하므로, 물고기의 정보는 리스트에 담아 인덱스로 식별할 수 있겠다. 백트래킹으로 접근하게 될 것이므로 재귀함수 형태로 문제에서 주어진 상황을 구현해야 한다. 구현하는 것은 두 가지로, 물고기를 이동시키는 것과 상어가 이..

문제 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다. 모노미노도미노 게임 보드 이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다. 모노미노도미노 게임에서 사용하는 블록 블록을 놓을 위치를 빨간색 보드에서 선택하면, 그 위치부터 초록색 보드로 블록이 이동하고, 파란색 보드로 블록이 이동한다. 블록의 이동은 다른 블록을 만나거나 보드의 경계..

문제 17825번: 주사위 윷놀이 (acmicpc.net) 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 풀이 1 문제에서, 같은 칸에 동시에 여러개의 말이 중복해서 존재할 수 없다는 조건이 있다. 즉 말을 이동하기 전, 해당 말이 이미 도착했는지, 혹은 해당 말이 이동하려는 칸이 이미 점유 중인지 따져봐야한다. 말이 도착할 수 있는 칸의 종류는 총 세가지 이다. 첫째로 도착칸을 지나간 경우, 둘째로 일반칸에 도착하는 경우, 셋째로 파란칸에 도착하는 경우이다. 파란칸에 도착하는 경우 진행방향이 바뀌는 점을 유의해야한다. 말이 진행할 수 있는 루트는 총 네가지로 볼 수 있다. 시작 -> 일반 -> 도착 시작 -> 10 -> 도착 시작 -..

문제 17837번: 새로운 게임 2 (acmicpc.net) 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 풀이 1 전체 보드의 크기는 최대 12^2 = 144인 반면, 주어지는 말의 개수는 최대 10개밖에 안된다. 따라서 이 문제의 경우, 주어진 제한조건에 따라 말의 데이터를 따로 배열에 넣어놓고 탐색하는 방법이 유효하다고 판단 가능하다. 문제에서 조건으로 생각해야하는 것은 보드 경계와 각 칸의 색깔이다. 조건에 의해 보드 경계 바깥으로 나가는 경우와 파란색 칸으로 가는 경우는 동일하게 취급되며, 앞 뒤..

문제 17779번: 게리맨더링 2 (acmicpc.net) 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 풀이 1 두 코드를 잘 비교해보자. N = int(input()) A = [[0]*(N+1)] sum_total = 0 for _ in range(N): li = [] for elem in map(int, input().split()): li.append(elem) sum_total += elem A.append([0] + li) def get_result(x,y,d1,d2): p_list = [0]*6 col..

문제 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다. 블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 그룹에 ..

문제 17142번: 연구소 3 (acmicpc.net) 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 1 이 문제는 언뜻 보면 지금껏 풀어온 탐색문제와 크게 다를것이 없어보이지만, 함정(?)이 숨겨져있어 주의가 필요하다. 문제를 자세히 읽어보며 어떻게 다른지 잘 파악해야 시간낭비없이 제대로된 설계로 문제를 풀이할 수 있다. 문제에서 원하는 상황은 "모든 빈 칸"에 바이러스가 퍼지는 상황이다. 따라서 바이러스 전염 구현이 끝나면 board를 탐색하며 '빈 칸'이 남아있는지 확인할 필요가 있는데, 답이 되는 '최소 ..