문제주어진 2차원 배열에서 각 칸에 고일 수 있는 물의 양을 계산하는 문제이다. 각 칸의 물 높이는 주변에 있는 벽(높이가 더 큰 칸들)에 의해 제한되며, 물은 낮은 칸을 채워 나가면서 주위 벽에 의해 막히는 곳에만 고일 수 있다.풀이이 코드의 핵심은 외곽부터 낮은 높이의 칸을 우선 탐색하면서 물을 채워나가는 것이다.먼저, 외곽에 있는 칸들을 힙에 추가하고 높이가 낮은 칸부터 탐색을 시작한다.탐색하면서 주변에 더 낮은 높이의 칸이 있다면, 현재 칸의 높이만큼 물을 채우고 채운 물의 양을 답에 더한다.물 높이와 상관없이 방문하지 않은 칸이라면 방문 처리 후, 현재 높이와 좌표를 힙에 추가하여 계속해서 주변을 탐색한다.이 과정을 통해 최종적으로 고일 수 있는 물의 양을 계산한다.Python 코드import ..
[백준 BOJ / Python] 22352번 항체 인식
문제주어진 격자 데이터의 전후를 비교하여 주입된 백신이 CPCU-1202 백신인지 판단하는 문제이다.CPCU-1202 백신을 놓으면, 백신이 주입된 조직에서 항체를 생성하고 같은 영역의 조직에 항체가 퍼진다.항체는 조직을 변형시켜 동일한 색상이거나 다른 색상이 될 수 있다. 풀이전체 조직의 영역들 중 색상이 바뀐 영역이 1개이하여야 한다.따라서 조직을 탐색하면서 동일한 영역이 변경된 것인지를 판단하고, 색상이 변경된 영역의 개수를 세어야 한다.BFS나 DFS를 통해 동일한 색상으로 이루어진 인접 영역을 탐색하며 해당 영역이 일관된 색상으로 변경되었는지 확인한다.탐색 중 영역이 다르다면 CPCU-1202 백신이 아님으로 NO를 출력하고,색상이 변경된 영역의 개수가 2개이상이어도 NO를 출력하며,그 외의 경..
문제통로에 음식물 쓰레기가 떨어져 있을 때, 인접한 쓰레기들끼리 하나의 덩어리로 보고 그중 가장 큰 덩어리의 크기를 구하는 문제이다. 인접한 음식물 쓰레기는 상하좌우로 붙어있는 경우를 말한다.풀이이 문제는 인접한 영역을 탐색하는 그래프 탐색 문제이다.BFS나 DFS를 활용해 연결 여부를 탐색하며 덩어리의 크기를 계산하면 된다.먼저 음식물 쓰레기의 영역을 입력받는다.이때, 쓰레기가 없는 상태는 1, 쓰레기가 있는 상태는 0으로 표시한다. (visited를 사용하지 않고 쓰레기가 있는 곳의 방문 여부를 쉽게 체크할 수 있다.)인접 칸을 탐색했을 때, 다음칸으로 이동 가능하면 쓰레기 영역 크기를 늘리고 방문 표시를 해준다.max를 사용해 가장 큰 쓰레기 크기를 갱신한다.Python 코드import sysfro..