[백준/Python] 14502번(완탐, DFS)_연구소

📌문제 유형

구현, 브루트포스, DFS (골드 Lv.4)

 

📌문제

14502번: 연구소

 

📌나의 문제풀이

- 0인 좌표 따로 저장 → combinations 이용해서 0인 좌표 중 3개 조합 만들기

- 조합 전체 실행 : 3개 1로 만들고, 이후 2 퍼지도록 dfs 이용

• 해당과정에서 maps를 다시 이용해야하므로, deepcopy 이용하여 maps 원상태 불러오기

# 풀이 방법
# 0인 좌표 받기 -> 3개 combination 
# 3개 1로 설정 -> 2는 dfs로 퍼트리기 -> 남는 0의 개수 세기

from itertools import combinations
from copy import deepcopy

n, m = map(int,input().split())

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

# 0인 좌표 넣기
wall_candidate = []
for x in range(n):
    for y in range(m):
        if maps[x][y] == 0:
            wall_candidate.append((x,y))

def dfs(i,j):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]

    if new_maps[i][j] != 2:
        return

    for k in range(4):
        nx = i + dx[k]
        ny = j + dy[k]

        if 0 <= nx < n and 0 <= ny < m:
            if new_maps[nx][ny] == 0:
                new_maps[nx][ny] = 2
                dfs(nx,ny)

# 3개 combination 
ans = 0
combi = list(combinations(wall_candidate, 3))
for dirs in combi:
    new_maps = deepcopy(maps)
    cnt = 0
    for d in dirs:
        new_maps[d[0]][d[1]] = 1
    # 2로 퍼트리기
    for i in range(n):
        for j in range(m):
            if new_maps[i][j] == 2:
                dfs(i,j)
    # 0 개수 세기
    for i_ in range(n):
        cnt += new_maps[i_].count(0)

    if cnt > ans :
        ans = cnt

print(ans)

 

 

📌 다른사람의 문제풀이

- BFS 활용 방법

[BOJ/백준] 14502번 연구소 (Python 파이썬)

from collections import deque
import copy

def bfs():
    queue = deque()
    tmp_graph = copy.deepcopy(graph)
    for i in range(n):
        for j in range(m):
            if tmp_graph[i][j] == 2:
                queue.append((i, j))

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if tmp_graph[nx][ny] == 0:
                tmp_graph[nx][ny] = 2
                queue.append((nx, ny))

    global answer
    cnt = 0

    for i in range(n):
        cnt += tmp_graph[i].count(0)

    answer = max(answer, cnt)


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

n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(n):
    graph.append(list(map(int, input().split())))

answer = 0
makeWall(0)
print(answer)

- DFS 활용

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())))

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

    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)

 

📌 리뷰

- 반복적으로 원 maps를 사용해야하는 경우, deepcopy 이용하기 

 

12. 얕은 복사(shallow copy)와 깊은 복사(deep copy)