<PART 3> Q16.백준 14502번: 연구소

https://www.acmicpc.net/problem/14502

14502번: 연구소

- pypy3 제출(python3 제출시 시간 초과)

#14502번 Q16.연구소
#사방으로 퍼지므로 dfs
#맵크기 입력받기
n, m =map(int,input().split())
 
#맵 정보 받기
graphs = []
for i in range(n):
    graphs.append(list(map(int,input().split())))
 
#벽 설치할 리스트 생성
temp = [[0]*m for _ in range(n)]
 
#상하좌우 이동
dx = [-1,1,0,0]
dy = [0,0,-1,1]
 
#결과값
result = 0
 
def virus(x,y):
    #virus가 사방에 퍼지도록
    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:
            #이동했을때 0인 경우만 2로 변경
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                virus(nx,ny) #재귀적으로 이동위치에서 상하좌우 이동
 
#temp에서 0의 갯수 세기
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개 있다면 바이러스 퍼뜨리고 score 찾기
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = graphs[i][j]
        #퍼뜨릴때 시작 위치는 2인 자리
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i,j)
        #다퍼뜨렸다면 score세기
        result = max(result,get_score())
        return
    # 벽을 차례대로 설치하기
    for i in range(n):
        for j in range(m):
            if graphs[i][j] == 0:
                graphs[i][j] = 1
                count += 1
                dfs(count)
                graphs[i][j] = 0
                count -= 1
 
dfs(0)
print(result)
 

dfs개념을 알고있어도 문제의 풀이 방향에 따라서 감을 전혀 못잡겟다. 벽을 3개를 차례대로 세울 때 어떻게 dfs를 적용시킬지에 대한 생각을 아예 떠올리지 못했다. 언젠가는 이것도 익숙해지는 순간이 올 것이다.
result = max(result,get_scoer()) 같은 방법은 이제 익숙해졌다. 이 문제에서는 벽을 차례대로 3개를 세우는 방법이 핵심인 것 같다. 이번 기회에 익숙해져야겠다.