연구소 [백준 14502]

문제

---

연구소 [백준 14502]
https://www.acmicpc.net/problem/14502

풀이

---

dfs나 bfs를 이용하여 문제를 해결할 수 있다. 가로 세로 크기가 그리 크지 않기 때문에 0인 인덱스 중 3개를 뽑아 벽을 세우는 조합의 경우의 수를 모두 검사하여도 시간이나 메모리가 초과되지 않는다. 다음 문제는 dfs 와 bfs 두 방법 모두 풀어도 문제가 딱히 없기 때문에 두 방법 모두 풀어보았다.

중요한 점

• 벽을 만드는 함수에서 벽이 3개가 되었을 때 return을 넣어주지 않았더니 계속해서 많은 함수가 호출되어 실행이 끝나지 않았다. 당연한 것이지만 까먹지 않도록 하는 게 좋을 거 같아 넣었다.
• dfs의 방법으로 문제를 풀 때 기존 board을 변화시키지 않기 위해 새로운 board를 만들어 해당 리스트만 값 변화를 하려 했는데 이 때 board를 복사하는 경우에 처음에는 deepcopy 방법을 택했는데 출력값이 제대로 나오지 않았고 이중 for문으로 인덱스 하나하나를 복사해줬을 때는 멀쩡한 값이 나오는 것을 확인했다. 아무래도 virus 함수에서 new_board를 참조할 때 전역에 있는 new_board를 선언한 것과 dfs 함수안에서의 것과 헷갈리는 것 같았다.

코드

---

dfs

import copy

n, m = map(int, input().split())
board = []
new_board = [[0] * m for _ in range(n)]
for _ in range(n):
    board.append(list(map(int, input().split())))
    
result = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def virus(x, y):    #바이러스가 상하좌우로 퍼지는 코드
    for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if new_board[nx][ny] == 0:  #아무것도 없으면 바이러스가 퍼짐
                    new_board[nx][ny] = 2
                    virus(nx, ny)   #다시 호출
def dfs():
    global result # key
    # new_board = copy.deepcopy(board)
    for i in range(n):  #new board에 복사
        for j in range(m):
            new_board[i][j] = board[i][j]
            
    for i in range(n):  #바이러스가 있으면 virus 호출
        for j in range(m):
            if new_board[i][j] == 2:
                virus(i, j)
    score = 0
    for i in range(n):
        for j in range(m):
            if new_board[i][j] == 0:
                score += 1
    result = max(result, score) # 전역변수 result와 지금상태에서의 score를 비교해서 최대를 보존
    return

def make_wall(cnt): # 벽 3개를 세우는 코드
    if cnt == 3:
        dfs()
        return # key
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                board[i][j] = 1
                make_wall(cnt + 1)
                board[i][j] = 0    
make_wall(0)
print(result)

bfs

---

from collections import deque
import copy
n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
visited = [[False] * m for _ in range(n)]
result = 0
def bfs():
    global result # key
    new_board = copy.deepcopy(board)
    q = deque()
    for x in range(n):
        for y in range(m):
            if new_board[x][y] == 2:
                q.append((x, y))
    while q:
        now_x, now_y = q.popleft()
        #if not visited[now_x][now_y]:
        for i in range(4):
            nx = now_x + dx[i]
            ny = now_y + dy[i]
            if nx >= 0 and nx < n and ny >= 0 and ny < m:
                if new_board[nx][ny] == 0:
                    new_board[nx][ny] = 2
                    q.append((nx, ny))
                        #visited[now_x][now_y] = True
    score = 0
    for i in range(n):
        for j in range(m):
            if new_board[i][j] == 0:
                score += 1
    result = max(result, score)
    return

def make_wall(cnt):
    if cnt == 3:
        bfs()
        return # key
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                board[i][j] = 1
                make_wall(cnt + 1)
                board[i][j] = 0    

make_wall(0)
print(result)