안녕

0. 문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 1. 풀이 방법 문제에서는 맨 가장자리엔 치즈가 없다라고 되어있다. 따라서 BFS의 시작은 맨 가장자리인 [0][0]에서 시작한다. 치즈와 인접한 공기를 체크하기 위해 adjCheck를 사용했다. 해당 리스트는 치즈와 인접한 공기의 개수를 체크한다. 공기의 중복 방문 처리를 위하여 airCheck를 사용했다. 해당 리스트는 공기가 이미 방문한 곳을 처리한다. 결론적으로..

0. 문제 링크 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 1. 풀이 방법 나는 맵에다가 직접 뱀의 몸을 그려서 해결하였다. 사과가 있는 곳은 0, 뱀이 있는 곳은 1, 빈 공간은 -1로 처리하였다. dict를 사용해서 특정 시간의 뱀의 위치 전환을 표시했다. -> 0~3까지의 인덱스로 관리하였음. R이면 인덱스 += 1 뱀의 머리가 방향을 전환했다 하더라도, 꼬리는 나중에 전환하므로, 꼬리의 방향 전환을 위한 tailMove를 추가로 생성해 준..

0. 문제 링크 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 1. 풀이 방법 DP를 이용해서 풀었다. 장난감은 중간 부품, 기본 부품 들로 만들 수 있는데, 우선 기본 부품으로 만들 수 있으면 기본 부품으로 만든다. 장난감을 만들 수 있는 중간 부품 또한 어떤 중간 부품이 필요할 수 있다. 따라서 재귀를 통해 중간 부품을 만들 수 있는 기본 부품들을 구한다. 이런 식으로 재귀를 통해 장난감까지 올라가면, 장난감을 ..

0. 문제 링크 https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 1. 풀이 방법 BFS + 구현으로 문제를 풀었는데, 방문 처리가 가장 중요한 문제이다. 방문 처리와 더불어서 어떤 조건일 때 방문을 허락할지도 잘 체크해야 한다. 방문 처리는 비트 2개를 사용해서 해결하였다. 0은 미방문, 1은 가로가 방문, 2는 세로가 방문, 3은 가로세로 모두 방문 어떤 조건일 때 방문을 허락할지는 구현 문제이므로 이건 생략하겠다. 2..

0. 문제 링크 https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 1. 풀이 방법 맨 처음 페이를 기준으로 정렬하고, 페이에 따른 기한 날짜에 넣는다. 만약 이미 그 기한 날짜에 다른 강의가 있다면 시간을 하루씩 당겨서 넣을 수 있는지 체크한다. 추가로 go to this day를 만들어서, 특정 기한 날짜의 강의는 this day의 날짜부터 강의를 할 수 있다고 정의한다. 또한 capacity를 만들어서, c..

0. 문제 링크 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 1. 풀이 방법 다들 적군이 내려온다고 생각하는데, 나는 그냥 궁수가 올라가는 방식을 사용했다. 궁수가 적을 찾는 과정은 (우선순위에 따라)BFS로 해결하였고, 적을 찾으면 적의 위치를 반환하였다. 여러 궁수가 같은 적을 찾는 경우를 고려하여 적의 위치를 set으로 해결하였다. 궁수의 자리는 조합을 이용하여 BF하게 해결하였다. 2. 코드 import sys from itertools imp..

0. 문제 링크 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 1. 풀이 방법 문제는 위상정렬로 해결하였다. 다만 여기서는 중복이 발생할 수 있는데, 해결법은 두 가지로 나뉜다. set을 사용해서 후순위 노드를 하나만 집어넣고, degree도 1만 추가한다. list를 사용해서 후순위 노드를 (중복일지라도) 여러 개 집어넣고, degree도 여러 번 추가한다. 2.2번 해결법을 사용하면, 속도는 느려진다. 아무튼 최종적으로..

0. 문제 링크 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 1. 풀이 방법 방향의 우선순위는 무조건 오른쪽 위, 오른쪽, 오른쪽 아래로 해야 한다. 그리고 왼쪽 상단부터 왼쪽 하단으로 차례로 돌면서 길을 찾는다. 나는 따로 방문 표시 복구를 하지 않았는데, 어차피 위에서 가지 못한 길이라면, 아래에서도 가지 못하는 길이기 때문에 복구하지 않았다. 따라서 dfs로 문제를 풀었다. 2. 코드 import sys input = sys.stdin.readline..

0. 문제 링크 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 1. 풀이 방법 BFS 문제이고, 방문 표시를 잘해야 한다. 특정 키를 가지고 있음을 비트로 표현하는데, 방문 표시는 특정 키들을 가지고 이 칸에 방문한 적이 있느냐? 가 되겠다. 따라서 키는 총 6개이므로, 000 000 ~ 111 111의 경우의 수를 가질 수 있다. 따라서 총 64개의 경우의 수가 존재한다. 이제부터 모든 칸을 돌면서 특정 비트(..

0. 문제 링크 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 풀이 방법 육지를 찾으면 BFS를 통해 육지를 모두 같은 그룹 번호로 지정한다. BFS를 하면서 육지의 가장자리를 찾게 된다면 가장자리 BFS에 저장한다. 모든 육지를 찾으면 위에서 저장한 가장자리 BFS로 다른 육지를 탐색한다. 이때 나와 같은 그룹 번호를 찾는다면 패스하고, 다른 육지 번호일 때만 최단 거리를 업데이트한다. 만약 바다에서 BFS 하던 도중 기존의 최단 거리보다 ..