연구소

문제 설명

https://www.acmicpc.net/problem/14502
<입력>
<출력>
<예시>

---

나의 풀이

충분히 할 수 있는데, 왠지 헷갈리는 게 너무 많아 처음 구현할 때는 정말 오래 걸렸다...

import copy
from itertools import combinations

n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

# 벽을 세울 수 있는 좌표 모두 알아내기
arr = []
for x in range(n):
    for y in range(m):
        if graph[x][y] == 0:
            arr.append((x, y))

# 그 중에 순서 상관 없이 3개 뽑는 모든 조합 알아내기
wall_3 = list(combinations(arr, 3))

# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 0의 개수 알아내는 함수
def count_0(graph):
    cnt = 0
    for x in range(n):
        for y in range(m):
            if graph[x][y] == 0:
                cnt += 1
    return cnt


# 바이러스 전파 함수
# 상하좌우가 0이라면 해당 자리를 2로 만든 후 바이러스 전파
def contaminate(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if not (nx >= n or nx < 0 or ny >= m or ny < 0):    
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                contaminate(nx, ny)

result = 0

# 모든 조합에 대해서 반복
for i in range(len(wall_3)):
    # 매번 temp를 원래 그래프로 초기화
    temp = copy.deepcopy(graph)

    # 해당 조합으로 일시적인 맵 설정
    for x, y in wall_3[i]:
        temp[x][y] = 1

    # 바이러스 전파
    for x in range(n):
        for y in range(m):
            # 해당 자리에 바이러스가 있을 경우 전염 함수 작동
            if temp[x][y] == 2:
                contaminate(x,y)
    
    # 바이러스 전파된 맵에 대하여 0의 개수 count
    # 0의 개수가 신고가를 찍으면 result 갱신
    result = max(result, count_0(temp))

print(result)

---

책 풀이

# BOJ에서는 [언어]를 PyPy3로 설정하여 제출해주세요.

n, m = map(int, input().split())
data = [] # 초기 맵 리스트
temp = [[0] * m for _ in range(n)] # 벽을 설치한 뒤의 맵 리스트

for _ in range(n):
    data.append(list(map(int, input().split())))

# 4가지 이동 방향에 대한 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0

# 깊이 우선 탐색(DFS)을 이용해 각 바이러스가 사방으로 퍼지도록 하기
def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 상, 하, 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if temp[nx][ny] == 0:
                # 해당 위치에 바이러스 배치하고, 다시 재귀적으로 수행
                temp[nx][ny] = 2
                virus(nx, ny)

# 현재 맵에서 안전 영역의 크기 계산하는 메서드
def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score

# 깊이 우선 탐색(DFS)을 이용해 울타리를 설치하면서, 매 번 안전 영역의 크기 계산
def dfs(count):
    global result
    # 울타리가 3개 설치된 경우
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j]
        # 각 바이러스의 위치에서 전파 진행
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i, j)
        # 안전 영역의 최대값 계산
        result = max(result, get_score())
        return
    # 빈 공간에 울타리를 설치
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                count += 1
                dfs(count)
                data[i][j] = 0
                count -= 1

dfs(0)
print(result)

---

느낀 점

1. 순열 조합 헷갈리지 말자.

from itertools import permutations, combinations
순열 = list(permutaions(items, n))
조합 = list(combinations(items, n))

2. 두 번째 코드에서 뭐가 잘못됐었나.

def contaminate(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if not (nx >= n or nx < 0 or ny >= m or ny < 0):    
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                contaminate(nx, ny)

def contaminate(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= n or nx < 0 or ny >= m or ny < 0:
    	    return
        if temp[nx][ny] == 0:
            temp[nx][ny] = 2
            contaminate(nx, ny)

두 번째 코드처럼 저렇게 하면 상하좌우 중 만약 상에서 범위를 벗어날 경우 뒤의 하좌우는 체크되지 못한 채로 루프가 끝난다.
앞 코드처럼 하거나 return 대신 continue를 쓰거나 하면 된다.
루프에서 pass, continue, break, return 의 개념 헷갈리지 말자.