implementation
[백준] 13460. 구슬 탈출 2 - Python
[Gold I] https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 조금 복잡했던 BFS 시뮬레이션 문제. 이동 시 빨간 구슬과 파란 구슬이 겹쳤을 때, 각각의 이동 횟수를 계산하여 처리하는 방식이 키포인트. BFS의 visited 처리는 빨간 구슬과 파란 구슬의 좌표를 이용한다. 몇 번째 이동인 지는 visited로 확인할 필요 없음. 자세한 풀이는 코드의 주석을 참고하여 확인하면 쉽게 이해..
[백준] 9328. 열쇠 - Python
[Gold I] https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 풀이 시간초과와 메모리 초과를 몇 번 받다가, 이리저리 최적화하여 Accepted 받은 문제. 처음엔 [백준] 1194. 달이 차오른다, 가자. 와 비슷해 보여, 비슷하게 Bitmasking을 이용해 풀이할까 생각했지만, 가능한 열쇠의 개수가 26개이므로, 2^26의 경우의 수를 모두 저장할 수는 없어, 다른 방법을 생각했다. 우선 그래프(지도)의 형태를 입력받을 때, 겉을 빈 공간('..
[백준] 20056. 마법사 상어와 파이어볼 - Python
[Gold IV] https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 풀이 지시하는 대로 구현하면 어렵지 않게 풀이할 수 있는 구현 문제. 파이어볼이 이동할 때 MOD연산을 활용하는 것과 질량이 0이 된 파이어볼을 제대로 제거하는 것에 유의하자. AC. N, M, K = map(int, input().split()) # 방향 (r이동량, c이동량) directions = [[-1, 0], [-1, 1], [0..
[백준] 14719. 빗물 - Python
[Gold V] https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 아이디어를 생각해내기가 조금 어렵지만, 그것만 생각해낸다면 쉽게 풀이할 수 있는 문제. 모든 열에 대하여, 그 칸의 왼쪽과 오른쪽 열의 최댓값을 구하고, (line 7, 8) 왼쪽과 오른쪽의 최댓값 중 더 작은 것에서 현재 열의 칸 수를 빼면 받을 수 있는 빗물의 양이 된다. (line 9) AC. H, W = map(int, input().split()) ..
[백준] 2638. 치즈 - Python
[Gold III] https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 "두 변 이상 치즈 외부 공기와 접촉" 한다는 조건만 잘 처리해 준다면, N, M (5 ≤ N, M ≤ 100) 이기 때문에 나머지는 Brute-Force로 처리해도 해결되는 문제이다. air 2차원 배열을 생성하여, 모든 칸을 순회하며, 외부 공기와 접촉한 공기 칸을 체크한다. 이 때, air 배열의 모든 칸은 1로 초기화하고, 외부와 닿아 있는 공기 칸일 ..
[백준] 2615. 오목 - Python
[Silver I] https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 풀이 19x19의 모든 칸을 순회하며, 오목이 되는 지 여부를 Brute-Force로 검사하면 된다. 오목이 될 수 있는 모든 경우는 하향 직선 5개, 우하향 대각성 5개, 우향 직선 5개, 우상향 대각선 5개가 이어지는 4가지의 경우가 존재하며, 시작하는 돌의 바로 이전 칸과, 5개째가 아닌 6개째의 칸까지 같이 확인하여 6목이 되지 않는 지를 검사해야 한다. AC. b = ..
[백준] 17144. 미세먼지 안녕! - Python
[Gold IV] https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 확산 과정과 공기청정기가 작동하는 과정을 문제에서 지시한 대로 정확하게 구현하면, 어렵지 않게 풀 수 있었던 문제. 다만 확산 과정에서, 새로운 배열을 생성하여 확산 과정을 기록하지 않으면, 다른 칸을 확산시키면서 값이 변하여 확산되는 미세먼지의 양이 변할 수 있으므로, 새로운 배열을 생성하여 계산한 이후 deep copy로 복사하여 다시 다음 과정을 진행시킨다. (new..