[python] 백준 14502번 : 연구소 (DFS, combinations)

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

14502번: 연구소

 

1. 코드 구현

import sys

n,m = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(n)]
tmp = [[0]*m for _ in range(n)]
# tmp = [[] for _ in range(n)]

dx = [0,1,0,-1]
dy = [1,0,-1,0]

# 바이러스 전파
def virus(x,y):
    for i in range(4):
        xx = x+dx[i]
        yy = y+dy[i]
        if 0<=xx<n and 0<=yy<m and tmp[xx][yy]==0:
            tmp[xx][yy]=2
            virus(xx,yy)

#안전영역 개수 구하기
def Count():
    cnt=0
    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 0:
                cnt+=1
    return cnt

def DFS(count):
    global result
    if count == 3:
        for i in range(n):
            for j in range(m):
                tmp[i][j] = lab[i][j]
                # tmp[i].append(lab[i][j])

        for i in range(n):
            for j in range(m):
                if tmp[i][j]==2:
                    virus(i,j)
        result = max(result, Count())
        return
    else:
        for i in range(n):
            for j in range(m):
                if lab[i][j] == 0:
                    lab[i][j]=1
                    count+=1
                    DFS(count)
                    lab[i][j]=0
                    count-=1
result=0
DFS(0)
print(result)

 

 

2. 다른 풀이 

from itertools import combinations

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]


#바이러스 전파
def virus(tmp, x, y):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]

    for k in range(4):
        xx = x+dx[k]
        yy = y+dy[k]
        if 0<=xx<n and 0<=yy<m and tmp[xx][yy] == 0:
            tmp[xx][yy] = 2
            virus(tmp, xx, yy)


def count(tmp):
    cnt = 0
    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 0:
                cnt += 1
    return cnt


def solution():
    result = 0
    tmp = [[0]*m for _ in range(n)]

    # 빈칸 좌표 구하기
    zeroIdxs = []
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                zeroIdxs.append((i, j))

    for coordinates in list(combinations(zeroIdxs, 3)):
        # 3개의 빈벽에 벽 설치
        for coordinate in coordinates:
            x, y = coordinate
            board[x][y] = 1

        # 바이러스를 전파시킬 임시 2차원 연구소 생성
        for i in range(n):
            for j in range(m):
                tmp[i][j] = board[i][j]

        # 바이러스 감염
        for i in range(n):
            for j in range(m):
                if tmp[i][j] == 2:
                    virus(tmp, i, j)

        result = max(result, count(tmp))

        # 설치한 벽 제거
        for coordinate in coordinates:
            x, y = coordinate
            board[x][y] = 0
    return result


print(solution())

 

3. 생각해볼 거리

PyPy3로는 성공했으나 Python3로는 시간초과가 발생하였다. 이러한 경우 input() 대신에 sys 라이브러리의 sys.stdin.readline()을 사용하여 데이터를 입력 받으면 문제를 해결할 수 있다. 

import sys

# a = input() 와 같은 의미 
a = sys.stdin.readlin()