방화벽 설치하기 (연구소)

문제 출처 : 코드트리_방화벽 설치하기
티어 : 골드4
유형 : 백트래킹, BFS
출제 : 2017년 상반기 오후 2번
주의사항 : 백트래킹같은 재귀함수 문제는 디버깅이 어려우므로 주의할 것.

---

첫 번째 문제와 비슷한 난이도로 출제된 두 번째 문제입니다. 첫 문제는 BFS, 두 번째 문제는 BFS가 섞인 재귀 문제를 내니 이때부터 그래프 문제를 본격적으로 내기 시작했다는 것을 알 수 있겠습니다. 현재에도 반드시 한 문제는 포함하고 있으므로, 그래프의 마스터가 되는 것을 목표로 공부해봅시다!

---

생각의 흐름

놓을 수 있는 벽이 최대 3개이므로, 빈 칸들 중에서 벽을 놓을 곳 3개를 고르는 조합 문제라고 생각을 했습니다. 따라서 벽을 놓을 수 있는 후보들을 wall cand list에 담고, 반복문을 이용하여 wall list에 세 개씩 차례대로 담아서, 그 wall list를 이용해 불이 얼마나 퍼질 수 있는지 검사하는 플랜을 세웠습니다. 또한 각 상황마다 그래프를 복사하여 temp_graph에서 불을 퍼트리도록 하여 원 그래프의 손상을 막았는데, 생각해보면 visited배열같은걸 매번 생성해서 할 수도 있겠다는 생각이 듭니다. 하여튼 이런 생각을 하고 풀이에 돌입했습니다.

 

스킬

저는 원 그래프가 변형되는 것을 원하지 않았기 때문에 복사된 그래프를 사용했는데, 여기서 그래프를 복사하는 방법을 알아보겠습니다. 보통 우리가 파이썬에서 그래프를 복사한다면 copy 라이브러리를 사용하게 됩니다. 그렇지 않으면 주소값을 복사해오게 되어 복사된 그래프의 변형이 원 그래프에까지 미칠 수 있기 때문입니다.

 

하지만 copy를 이용하면 시간이 너무 오래 걸리게 됩니다. 그래서 그래프를 복사할 수 있는 또 다른 방법인 리스트 컴프리헨션(list comprehension)을 소개드리겠습니다. 리스트 컴프리헨션은 리스트 안에서 반복문과 조건문을 이용해 리스트를 간결하게 표현하는 방법입니다. 조건문까지 쓰는 문제는 나오지 않으니, 반복문을 위주로 보여드릴게요. 1부터 5까지 들어있는 1차원 리스트를 만드는 방법에는 무엇이 있을까요?

a = [1, 2, 3, 4, 5]

 

 

로 나타내는 방법이 있겠네요. 그럼 1부터 50까지는요? 50까지를 하나하나씩 쓰는건 너무 고통이니까, 반복문을 이용해 나타내 봅시다.

a = []
for i in range(1, 51):
    a.append(i)

 

이 방법을 이용하면 1부터 50까지 들어있는 리스트를 만들 수 있을 것 같습니다. 하지만 리스트 하나 만드는데 세 줄이나 필요할까요?

a = [i for i in range(1, 51)]

 

라는 코드 한 줄이면 우리는 위와 똑같은 리스트를 만들 수 있습니다. 마찬가지로, 2차원 그래프를 만들 때도 비슷하게 만들 수 있는데, 1부터 9까지 3x3로 구성된 2차원 리스트를 만들어 보겠습니다.

a = [[3*j+i for i in range(1, 4)] for j in range(3)]
# a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

 

사용법이 대략 감이 가시나요? j의 3번의 반복에 대해서, 각 i가 작동하며 그 값을 리스트에 넣어주는 것입니다. 이와 같은 방식으로 2차원 그래프를 복사할 수 있겠습니다. 코드는 아래와 같습니다.

a = [[row for row in rows] for rows in graph]

 

풀이

from collections import deque

def getInput():
    # 입력받는 함수
    global N, M, R, graph, firelist, wallcandlist
    N, M = map(int, input().split())
    graph = []
    firelist = []
    wallcandlist = []

    for i in range(N):
        a = list(map(int, input().split()))
        for j in range(M):
            if a[j] == 0:
                wallcandlist.append((i,j))
            elif a[j] == 2:
                firelist.append((i,j))
        graph.append(a)

    R = len(wallcandlist)

def fire(walllist):
    # 불을 전파하며 영역을 세어주는 함수
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    temp_graph = [[arr for arr in arrs] for arrs in graph]
    
    for x, y in walllist:
        temp_graph[x][y] = 1
    
    for xx, yy in firelist:
        q = deque([(xx,yy)])

        while q:
            x, y = q.popleft()

            for i in range(4):
                nx = x+dx[i]
                ny = y+dy[i]
                if 0<=nx<N and 0<=ny<M and temp_graph[nx][ny] == 0:
                    temp_graph[nx][ny] = 2
                    q.append((nx,ny))
    ccnt = 0
    for i in range(N):
        for j in range(M):
            if temp_graph[i][j] == 0:
                ccnt += 1
    return ccnt

def dfs(level, index):
    # dfs를 실행하는 함수
    global cnt
    if level == 3:
        cnt = max(cnt, fire(walllist))
        return
    for i in range(index, R):
        walllist.append(wallcandlist[i])
        dfs(level+1, i+1)
        walllist.pop()


# ===== 실제 실행하는 부분 =====
def main():
    global cnt, walllist

    cnt = -1
    walllist = []
    getInput()
    dfs(0, 0)
    print(cnt)

main()