simulation
[백준] 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로 확인할 필요 없음. 자세한 풀이는 코드의 주석을 참고하여 확인하면 쉽게 이해..
[백준] 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..
[백준] 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로 초기화하고, 외부와 닿아 있는 공기 칸일 ..
[백준] 17144. 미세먼지 안녕! - Python
[Gold IV] https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 확산 과정과 공기청정기가 작동하는 과정을 문제에서 지시한 대로 정확하게 구현하면, 어렵지 않게 풀 수 있었던 문제. 다만 확산 과정에서, 새로운 배열을 생성하여 확산 과정을 기록하지 않으면, 다른 칸을 확산시키면서 값이 변하여 확산되는 미세먼지의 양이 변할 수 있으므로, 새로운 배열을 생성하여 계산한 이후 deep copy로 복사하여 다시 다음 과정을 진행시킨다. (new..
[백준] 16236. 아기 상어 - Python
[Gold III] https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 우선 그래프 내에서 가장 가까운 칸을 찾기 때문에, BFS로 풀어야 하는 것은 바로 생각이 났고, N 가장 왼쪽 순으로 나열. return list(sorted(prey, key=lambda x: (x[0], x[1], x[2]))) second = 0 size = 2 eat = 0 while True: r, c = shark M[r][c] = size prey =..