출처: https://www.acmicpc.net/problem/14502
문제부터 분석해봅시다
해당 문제는 연구소의 지도가 입력으로 주어지고, 임의의 위치에 벽을 3개 세운 다음에 구할수 있는 안전지대의 최대 넓이를 구하는게 문제가 요구하는 바입니다.
위 문제는 아무리 봐도 bfs 혹은 dfs로 풀어야하는 유형입니다. 이 문제는 일단 bfs로 풀어보도록 하겠습니다.
일단 문제를 어떻게 풀지에 대해서 생각해보면, 다음의 방법이 떠오를겁니다.
- 일단 임의의 위치에 벽을 3개 세운다
- bfs로 탐색해서 안전지대의 넓이를 갱신한다
그런데 임의의 위치에 벽을 3개를 세워야하는데, 딱히 방법이 잘 떠오르지 않을수도 있습니다. 이거는 재귀함수로 해결을 하면됩니다! 다음과 같이 재귀함수를 작성하도록 하겠습니다.
- 탈출조건: 벽을 3개를 세우면, bfs로 탐색하고 안전지대 넓이를 갱신하고 탈출
- 점화식: 벽을 세우고, depth를 1 늘리고, 벽을 지운다
위의 방법대로 코드를 작성해보겠습니다.
코드를 소개하겠습니다.
from collections import deque
import sys
import copy
# 벽을 세우는 메소드. 벽을 3개 모두 세우면 bfs로 탐색을 시작한다
def wall(n):
if n == 3:
lab_param = copy.deepcopy(lab)
bfs(lab_param)
return
# depth별로 벽을 세워서 마지막에 bfs 탐색
for i in range(N):
for j in range(M):
if lab[i][j] == 0:
lab[i][j] = 1
wall(n + 1)
lab[i][j] = 0
# 해당 좌표에 바이러스를 퍼뜨릴 수 있는지 검사하는 메소드
def check(lab, x, y):
if x <= -1 or x >= M or y <= -1 or y >= N:
return False
if lab[y][x] == 0:
return True
return False
# 연구실의 정보가 주어지면 바이러스가 퍼진 영역의 개수를 갱신하는 메소드
def bfs(lab):
global answer
queue = deque()
cnt = 0
for i in range(N):
for j in range(M):
# 바이러스를 마주친경우
if lab[i][j] == 2:
# deque에 해당 좌표를 집어넣는다
queue.append((j, i))
# queue가 빌때까지 탐색
while queue:
# queue에서 좌표 하나 뽑아내기
v = queue.popleft()
# 해당 좌표 기준으로 상하좌우 탐색
if check(lab, v[0] - 1, v[1]) == True:
lab[v[1]][v[0] - 1] = 2
queue.append((v[0] - 1, v[1]))
if check(lab, v[0] + 1, v[1]) == True:
lab[v[1]][v[0] + 1] = 2
queue.append((v[0] + 1, v[1]))
if check(lab, v[0], v[1] - 1) == True:
lab[v[1] - 1][v[0]] = 2
queue.append((v[0], v[1] - 1))
if check(lab, v[0], v[1] + 1) == True:
lab[v[1] + 1][v[0]] = 2
queue.append((v[0], v[1] + 1))
# 안전영역 탐색
for i in range(N):
for j in range(M):
if lab[i][j] == 0:
cnt += 1
answer = max(answer, cnt)
input = sys.stdin.readline
N, M = map(int, input().split())
answer = 0
lab = [list(map(int, input().split())) for _ in range(N)]
wall(0)
print(answer)일단은 위의 문제에서는 3개의 함수가 등장합니다. 각각의 함수를 설명하겠습니다.
wall(n)
wall 함수의 경우 벽을 세우는 함수입니다.
일단 탈출조건부터 먼저 분석을 해보면, depth가 3인 경우에는 bfs로 map을 모두 읽어내고 안전지대의 넓이를 구해야하는데, 읽어내는 과정에서 바이러스에 감염된 좌표를 죄다 2로 바꿔줘야하기 때문에 lab을 deepcopy로 깊게 복사를 뜬 다음에 bfs로 모두 읽어냅니다.
그리고 점화관계는 매우 간단합니다. 좌표를 선형으로 촤르륵 읽어내고 재귀함수 방식을 이용해서 벽을 세우면됩니다.
check(lab, x, y)
입력받은 lab의 지도와 좌표 x, y를 받아서 해당 좌표를 바이러스에 감염시킬 수 있는지 여부를 반환하는 함수입니다.
일단 해당 좌표가 인덱스를 벗어났거나, 혹은 벽으로 막혀있다면 False를 반환하고, 빈 방인 경우에는 True를 반환해주면됩니다.
bfs(lab)
bfs 방식으로 lab을 탐색하는 메소드입니다.
lab의 좌표를 선형으로 읽어내서, 감염시킬 수 있는 좌표는 죄다 탐색을 통해 감염시키는 함수입니다.
해당 함수는 bfs 방식으로 동작하기 때문에 다음의 과정으로 동작합니다.
- 2를 가진 좌표를 만나면 해당 좌표를 queue에 넣습니다.
- queue가 빌때까지 queue에서 좌표를 꺼내고, 인접한 좌표가 감염 가능한지를 체크하고, 감염이 가능하면 해당 좌표를 감염시키고 그 좌표를 queue에 삽입한다.
- 1, 2번 과정을 계속 반복
- 반복이 모두 끝나면, 안전지대의 면적을 계산해서 answer를 갱신한다
위의 과정을 통해서 answer를 출력하면 문제는 모두 해결됩니다.
