성곽
-
[Python] 백준 2234 성곽알고리즘/문제풀이 2021. 10. 9. 15:41
1. 문제 링크 https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 2. 문제 요약 방의 개수 구하기 가장 넓은 방 구하기 하나의 벽 제거 시 가장 넓은 방 크기 구하기 3. 아이디어 정리 bfs를 이용하여 탐색을 한다. 방문 안 한 방 중 상하좌우 탐색하여 벽을 찾는다. 벽이 존재하는 경우 "3. 하나의 벽 제거 시 가장 넓은 방 크기 구하기"를 구하기 위해 근처 벽 변수에 넣어준다. 벽이 존재하지 않는 경우 현재 방의 크기를 늘려주고 de..