https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 요즘 비슷한 문제를 엄청 많이 풀었다. 다 거기서 거기네.. bfs... 비슷한 bfs 문제들 경쟁적 전염 연구소 감시 피하기 인구 이동 make_ripe 함수로 하루동안 토마토의 변화를 계산한다. 우선 익은 토마토가 있는 좌표들인 tomato를 큐로 만들고, 이들을 하나씩 pop하면서 그 토마토의 인접한 부분 중에 0인 곳이 있으면 1로 바꿔준다. 그리고 이제 익게 되었으니 다음..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net * Python으로는 시간 초과, PyPy3로는 통과 find_union 함수로는 현재 국가들 상태에서 국경 열 수 있는 국가들을 구합니다. 반환하는 것은 list of list인 unions로, 같은 연합국인 국가들의 좌표를 하나의 리스트로 저장합니다. 만약 연결되지 않는 연합국 그룹이 2개라면, unions는 2개의 리스트를 가진 리스트입니다. 모든 좌표에 대해 아직 방문하지 않..

https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 백준 연구소 문제와 유사하게 풀이했습니다. school엔 입력으로 받아들인 학교의 상태, teachers에는 모든 선생님들의 위치 좌표, blank에는 빈 곳의 위치 좌표를 저장합니다. teacher_detect 함수에선 한 명의 선생님이 감시할 수 있는 범위를 확인합니다. 입력으로 주어진 선생님의 위치 좌표에 대해, 그 좌표의 상하좌우를 순서대로 살펴봅니다. 현재 방향으로 이동하면서, ..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 최적의 벽 세우기를 알고리즘으로 생각하긴 너무 어려운 것 같아서.. 그냥 모든 combination으로 계산해보는 걸로 코드를 짜봤다. Python3으로는 시간초과고 PyPy3로는 통과라서 약간 찜찜하지만~ 그래도~~ 입력으로 주어진 연구소를 graph, 연구소에서 벽을 세울 수 있는 빈 곳의 좌표는 blank, 바이러스의 좌표는 virus에 저장했다. compute_safe 함수로는 입력으로 주어진 연구소 ..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 입력으로 주어진 수와 연산자를 저장합니다. 주어진 연산자 조건에 따라 가능한 모든 중복없는 배열을 permutated_operators에 저장하고, 각 배열마다 계산한 값을 vals에 저장합니다. 음수로 나누기를 할 땐 문제에서 주어진 조건에 맞게 변형 후 계산합니다. 이렇게 구한 값들중 최댓값과 최솟값을 차례로 프린트합니다. import s..

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 시험관의 상태를 n초마다 업데이트하여 풀이했습니다. 각 바이러스의 위치는 딕셔너리로 저장했고, 딕셔너리의 value는 큐로 만들어 처리 완료된 경우 pop할 수 있도록 했습니다. contaminate 함수를 통해 매 초마다 시험관을 업데이트 합니다. 1~K번 바이러스까지 차례대로 딕셔너리에 해당 바이러스 번호가 key로 있으면 해당 key의 모든 value들(좌표들)..