연구소 Python 정리 및 구현 (백준 14502, 삼성 SW 역량테스트 기출)

연구소 (백준 14502)

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

Abstract

• pypy3 환경

  • take 1: 3116ms
  • take 2: 892ms

---

Edge case

1. 문제조건

• 벽 3개를 완전 하나하나씩 다 대입해 봐야함
• DFS보다는 비재귀 형식의 BFS사용

2. 재귀

• deepcopy를 사용하여서 graph가 누적되지 않게

---

Code

1. BFS + 재귀를 이용한 벽 추출

설명 주석 참조

# 백준 14502
# 시작시간 15:13 - 16:13
# https://www.acmicpc.net/problem/14502
# 2초 제한 
import sys
import copy
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
check = [[0]*m for _ in range(n)]
answer = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

virus = list()


def bfs():
    global answer
    g = copy.deepcopy(graph)
    virus = deque()
    for r in range(n):
        for c in range(m):
            if graph[r][c] == 2:
                virus.append([r, c])
    while virus:
        x, y = virus.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 > nx or nx >= n or ny < 0 or ny >= m:
                continue
            if g[nx][ny] == 0:
                virus.append([nx, ny])
                g[nx][ny] = 2
    answer = max(cal(g), answer)
    

def cal(g):
    cnt = 0
    for r in range(n):
        for c in range(m):
            if g[r][c] == 0:
                cnt += 1
    return cnt

def wall(cnt):
    global answer
    if cnt == 3:
        bfs()
        return
    
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                wall(cnt + 1)
                graph[i][j] = 0
        
wall(0)
print(answer)

---

2. BFS + Combination

재귀적으로 벽을 생성하였던것을 Combination 함수를 이용하여 벽 생성

# 백준 14502
# 시작시간 15:13
# https://www.acmicpc.net/problem/14502
# 2초 제한 
import sys
import copy
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
check = [[0]*m for _ in range(n)]
answer = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

roc = list()
for r in range(n):
        for c in range(m):
            if graph[r][c] == 0:
                roc.append([r, c])

                
def combination(arr, n):
    result = []
    if n == 0:
        return [[]]
    for i in range(0, len(arr)):
        elem = arr[i]
        rest_arr = arr[i+1 : ]
        for c in combination(rest_arr, n-1):
            result.append([elem]+c)

    return result

def bfs(g):
    global answer
    virus = deque()
    for r in range(n):
        for c in range(m):
            if graph[r][c] == 2:
                virus.append([r, c])
    while virus:
        x, y = virus.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 > nx or nx >= n or ny < 0 or ny >= m:
                continue
            if g[nx][ny] == 0:
                virus.append([nx, ny])
                g[nx][ny] = 2
    answer = max(cal(g), answer)
    

def cal(g):
    cnt = 0
    for r in range(n):
        for c in range(m):
            if g[r][c] == 0:
                cnt += 1
    return cnt

def wall(cnt):
    global answer
    for wl in combination(roc, 3):
        g = copy.deepcopy(graph)
        for x, y in wl:
            g[x][y] = 1
        bfs(g)
        
wall(0)
print(answer)