[Python] 연구소(DFS/BFS)

문제

14502번: 연구소

입력

• 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
• 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
• 빈 칸의 개수는 3개 이상이다.

출력

• 첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

문제 풀이

• 벽 3개를 먼저 세워보기 (조합 라이브러리 or DFS 사용)
• 벽 3개가 세워졌다면, 바이러스를 퍼트릴 새로운 리스트에 그래프 값 복사
• 바이러스 퍼트리기 (이동하기 전 위치 값이 2이고, 이동할 위치의 값이 0인 경우)
• 바이러스 퍼트리기 까지 완료 했다면, 바이러스가 퍼진 후의 안전구역 크기 세기 (0의 개수 구하기)
• 다음 탐색을 위해 그래프 초기화 벽을 세운 곳의 값을 다시 0으로 변경 및, 벽의 개수 0개로 초기화
• 반복해서 탐색 진행
• 탐색을 진행할 때 마다 안전구역의 크기를 비교하여 최댓 값 구하기
• 안전구역의 최댓 값 출력

코드

# 방향이동
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
# 임계구역 계산 변수
result = 0
# 입력받기
n, m = map(int,input().split())
graph = []
wall_graph = [[0] * m for _ in range(n)]
for _ in range(n):
    graph.append(list(map(int,input().split())))

# dfs로 바이러스 퍼트리기
def virus(y,x):
    for i in range(4):
        new_y = y + dy[i]
        new_x = x + dx[i]
        if 0 <= new_y < n and 0 <= new_x < m :
            if wall_graph[new_y][new_x] == 0:
                wall_graph[new_y][new_x] = 2
                virus(new_y,new_x)
# 안전영역 크기 구하기
def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if wall_graph[i][j] == 0:
                score += 1
    return score

def dfs(count):
    global result
    # 벽 3개 인 경우 wall그래프에 graph값 복사
    if count == 3:
        for i in range(n):
            for j in range(m):
                wall_graph[i][j] = graph[i][j]
        # 바이러스 퍼트리기
        for i in range(n):
            for j in range(m):
                if wall_graph[i][j] == 2:
                    virus(i,j)
        # 0 개수 최대값 구하기
        result = max(result,get_score())
        return
    # 벽 3개 세우기
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                count += 1
                dfs(count)
                graph[i][j] = 0
                count -= 1
dfs(0)
print(result)