112. [삼성기출8]Python 백준 14502 번 연구소 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 14502 번 연구소 입니다.

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

14502번: 연구소

 

먼저 백준 14502 번 연구소 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

import sys
input = sys.stdin.readline
from itertools import combinations
from copy import deepcopy
N, M = map(int, input().split())
lab = []
for _ in range(N):
    lab.append(list(map(int, input().split())))

empty_loc = [(n, m) for n in range(N) for m in range(M) if lab[n][m] == 0]
virus_loc = [(n, m) for n in range(N) for m in range(M) if lab[n][m] == 2]

dir_x = [-1, 1, 0, 0]
dir_y = [0, 0, -1, 1]

def cnt_safe_zone(graph):
    cnt = 0
    for n in range(N):
        for m in range(M):
            if graph[n][m] == 0:
                cnt += 1
    return cnt

def spread_virus(graph, x, y):
    for i in range(4):
        nx = dir_x[i] + x
        ny = dir_y[i] + y
        if 0 <= nx < N and 0 <= ny < M:
            if graph[nx][ny] == 0:
                graph[nx][ny] = 2
                spread_virus(graph, nx, ny)

def make_wall(graph):
    global ans
    for walls in combinations(empty_loc, 3): #빈 공간에서 3개 조합 (안겹치게 벽 3개 세우기)
        tmp_graph = deepcopy(graph) #조합 할 때마다 그래프 딥카피

        for x, y in walls: #벽 3개 세우기
            tmp_graph[x][y] = 1 #벽 세우기

        for x, y in virus_loc: #바이러스 위치
            spread_virus(tmp_graph, x, y) #바이러스 dfs로 퍼트리기

        ans = max(ans, cnt_safe_zone(tmp_graph)) #다 퍼트렸으면 수 세고 업데이트

ans = 0
make_wall(lab)
print(ans)

 

문제 요약

연구소에서 바이러스가 유출됩니다.

바이러스의 확산을 막기 위해 총 3개의 벽을 세웁니다.

이때 벽의 위치에 따라 바이러스가 퍼지지 않는 지역인 안전 영역의 크기가 달라지는데

이 안전 영역의 최대 크기를 출력합니다.

 

문제 접근

연구소의 가로 세로 크기가 크지 않으므로

가능한 모든 위치에 벽을 세우고, 바이러스를 유출시켜 안전 영역의 최대 크기를 업데이트합니다.

 

이런식으로 모든 벽을 하나씩 세우면 시간초과가 나므로

def makeWall(cnt):
    if cnt == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                makeWall(cnt+1)
                graph[i][j] = 0

 

조합(combinations)을 이용해 더욱 효율적으로 해결할 수 있습니다.

def make_wall(graph):
    global ans
    for walls in combinations(empty_loc, 3): #빈 공간에서 3개 조합 (안겹치게 벽 3개 세우기)
        tmp_graph = deepcopy(graph) #조합 할 때마다 그래프 딥카피

        for x, y in walls: #벽 3개 세우기
            tmp_graph[x][y] = 1 #벽 세우기

        for x, y in virus_loc: #바이러스 위치
            spread_virus(tmp_graph, x, y) #바이러스 dfs로 퍼트리기

 

Python 코드 구현

 

먼저 필요한 라이브러리를 모두 가져옵니다.

import sys
input = sys.stdin.readline
from itertools import combinations
from copy import deepcopy

 

 연구소의 지도를 입력받습니다.

N, M = map(int, input().split())
lab = []
for _ in range(N):
    lab.append(list(map(int, input().split())))

 

 벽을 놓을 수 있는 빈 공간 좌표 리스트 empty_loc과 

바이러스 좌표 리스트 virus_loc을 구현합니다.

empty_loc = [(n, m) for n in range(N) for m in range(M) if lab[n][m] == 0]
virus_loc = [(n, m) for n in range(N) for m in range(M) if lab[n][m] == 2]

 

바이러스를 퍼트리기 위해 상하좌우 리스트도 구현합니다.

dir_x = [-1, 1, 0, 0]
dir_y = [0, 0, -1, 1]

 

먼저 안전영역의 크기를 구하는 함수입니다.

연구소를 순회하며 좌표가 0이면 cnt를 증가시키고 순회가 끝나면 그 값을 출력합니다.

def cnt_safe_zone(graph):
    cnt = 0
    for n in range(N):
        for m in range(M):
            if graph[n][m] == 0:
                cnt += 1
    return cnt

 

다음은 바이러스 위치를 입력받아 해당 지도에 dfs 방식으로 바이러스를 퍼트리는 함수입니다.

좌표가 들어오면 상하좌우를 살펴 다음 좌표가 지도 밖에 나가지 않는다면,

바이러스가 퍼질 수 있으면 퍼트리고, 해당 위치에서 다시 반복적으로 바이러스를 퍼트리는 함수입니다.

def spread_virus(graph, x, y):
    for i in range(4):
        nx = dir_x[i] + x
        ny = dir_y[i] + y
        if 0 <= nx < N and 0 <= ny < M:
            if graph[nx][ny] == 0:
                graph[nx][ny] = 2
                spread_virus(graph, nx, ny)

 

벽을 가능한 위치에 다 만들어보고, 안전영역의 최대값을 업데이트 하는 함수 make_wall 입니다.

1. combination에 아까 만들어뒀던 빈 공간 좌표를 3개를 조합합니다.

2. deepcopy를 이용해 그 좌표들에 벽을 세웁니다. 

3. 벽을 다 세웠으면 바이러스를 퍼트립니다.

4. 안전영역의 크기를 구한 후 최대 안전영역의 크기와 비교한 후 업데이트합니다.

def make_wall(graph):
    global ans
    for walls in combinations(empty_loc, 3): #빈 공간에서 3개 조합 (안겹치게 벽 3개 세우기)
        tmp_graph = deepcopy(graph) #조합 할 때마다 그래프 딥카피

        for x, y in walls: #벽 3개 세우기
            tmp_graph[x][y] = 1 #벽 세우기

        for x, y in virus_loc: #바이러스 위치
            spread_virus(tmp_graph, x, y) #바이러스 dfs로 퍼트리기

        ans = max(ans, cnt_safe_zone(tmp_graph)) #다 퍼트렸으면 수 세고 업데이트

 

이제 함수를 실행시키고, 출력만 하면 됩니다.

ans = 0
make_wall(lab)
print(ans)

 

파이썬 백준 14502 번 연구소 최종 코드입니다. 

import sys
input = sys.stdin.readline
from itertools import combinations
from copy import deepcopy
N, M = map(int, input().split())
lab = []
for _ in range(N):
    lab.append(list(map(int, input().split())))

empty_loc = [(n, m) for n in range(N) for m in range(M) if lab[n][m] == 0]
virus_loc = [(n, m) for n in range(N) for m in range(M) if lab[n][m] == 2]

dir_x = [-1, 1, 0, 0]
dir_y = [0, 0, -1, 1]

def cnt_safe_zone(graph):
    cnt = 0
    for n in range(N):
        for m in range(M):
            if graph[n][m] == 0:
                cnt += 1
    return cnt

def spread_virus(graph, x, y):
    for i in range(4):
        nx = dir_x[i] + x
        ny = dir_y[i] + y
        if 0 <= nx < N and 0 <= ny < M:
            if graph[nx][ny] == 0:
                graph[nx][ny] = 2
                spread_virus(graph, nx, ny)

def make_wall(graph):
    global ans
    for walls in combinations(empty_loc, 3): #빈 공간에서 3개 조합 (안겹치게 벽 3개 세우기)
        tmp_graph = deepcopy(graph) #조합 할 때마다 그래프 딥카피

        for x, y in walls: #벽 3개 세우기
            tmp_graph[x][y] = 1 #벽 세우기

        for x, y in virus_loc: #바이러스 위치
            spread_virus(tmp_graph, x, y) #바이러스 dfs로 퍼트리기

        ans = max(ans, cnt_safe_zone(tmp_graph)) #다 퍼트렸으면 수 세고 업데이트

ans = 0
make_wall(lab)
print(ans)

 

백준 14502 번 연구소 자세한 설명 및 Python 코드였습니다.

감사합니다.