[백준 14502] 연구소

1. 문제

www.acmicpc.net/problem/14502

14502번: 연구소

2. 접근 방법

벽을 3개씩 치면서 탐색을 하는 것임다

 

살짝 다른 점은

안전 영역 계산을 위해서

임시로 temp라는 2차배열을 만들어서 벽 3개를 넣은 board를 복사하는 것입니다. 

이 때 shallow copy가 되면 원본인 board에 영향을 끼치기 때문에 deep copy로 해주어야하는데,

import 하기 귀찮아서

사실은 코테에서 라이브러리 사용해도 되는지 ? 잘 모르기 때문에 요소 하나씩 넣어줬습니다.

 

deep copy를 쓸 경우에는 import copy 후 temp = copy.deepcopy(board)를 하면됩니다.

 

여튼 복사를 마친 후에 temp를 사용해 안전 영역을 계산해주고 안전영역 최댓값과 비교해서 result를 갱신해줍니다.

3. 코드

python

def isRoad(x, y):
    if 0 <= x < M and 0 <= y < N:
        return True
    return False

def virus(x, y):
    global dx, dy
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if isRoad(nx, ny):
            if temp[ny][nx] == 0:
                temp[ny][nx] = 2
                virus(nx, ny)

# 안전영역 크기 계산
def get_score():
    score = 0
    for y in range(N):
        for x in range(M):
            if temp[y][x] == 0:
                score += 1
    return score

def dfs(count):
    global result, N, M
    if count == 3:
        # board를 temp로 복제
        for y in range(N):
            for x in range(M):
                temp[y][x] = board[y][x]

        # 각 바이러스의 위치에서 전파 진행
        for y in range(N):
            for x in range(M):
                if temp[y][x] == 2:
                    virus(x, y)

        result = max(result, get_score())
        return

    for y in range(N):
        for x in range(M):
            if board[y][x] == 0:
                board[y][x] = 1
                count += 1
                dfs(count)
                board[y][x] = 0
                count -= 1


N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
temp = [[0]*M for _ in range(N)]

dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
result = 0

dfs(0)
print(result)

4. 마치며

.