[ BOJ ] DFS/BFS - 연구소

김우경·2020년 11월 15일
0

삼성기출

목록 보기
8/37

문제 링크

14502번: 연구소

문제설명

NM 크기의 연구소에 11인 각 칸은 빈칸 또는 벽으로 이루어져있음. 일부 칸은 바이러스가 존재하고, 바이러스는 상하좌우 인접한 빈칸으로 퍼져나감. 벽을 딱 3개만 세워서 얻을 수 있는 바이러스가 퍼질 수 없는 안전 영역 크기의 최대값은?

IN
N M
지도의 모양 (0:빈칸, 1:벽, 2:바이러스)

OUT
안전 영역의 최대 크기

문제풀이

접근

빈칸중 3개 고르기 → combination

바이러스 퍼뜨리기 → BFS 이용

시도 1

import sys
import copy
from collections import deque
input = sys.stdin.readline

answer = 0
n, m = map(int, input().split())
lab = []
for i in range(n):
    l = list(map(int, input().split()))
    lab.append(l)

def check(lab):
    queue = deque()
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 2:
                queue.append([i,j])
    print(queue)
    while queue:
        i,j = queue.popleft()
        if i-1>=0 and lab[i-1][j] == 0:
            lab[i-1][j] = 2
            queue.append([i-1, j])
        if i+1<n and lab[i+1][j] == 0:
            lab[i+1][j] = 2
            queue.append([i+1, j])
        if j-1>=0 and lab[i][j-1] == 0:
            lab[i][j-1] = 2
            queue.append([i, j-1])
        if j+1<m and lab[i][j+1] == 0:
            lab[i][j+1] = 2
            queue.append([i, j+1])
    print(lab)

def dfs(lab, count):
    if count == 3:
        global answer
        ans = 0
        viruslab = copy.deepcopy(lab)
        check(viruslab)
        for i in range(n):
            for j in range(m):
                if viruslab[i][j] == 0:
                    ans += 1
        answer = max(answer, ans)
        count = 0
    else:
        for i in range(n):
            for j in range(m):
                if lab[i][j] == 0:
                    lab[i][j] = 1
                    dfs(lab, count+1)
                    lab[i][j] = 0

dfs(lab, 0)
print(answer)

dfs를 이용하려고 했다. 근데 시간이 엄청 오래걸려서 시초 날거같음

시도 2

import sys
import copy
from collections import deque
import itertools
input = sys.stdin.readline

answer = 0
n, m = map(int, input().split())
lab = []
empty = []

for i in range(n):
    l = list(map(int, input().split()))
    for j in range(len(l)):
        if l[j] == 0:
            empty.append([i,j])
    lab.append(l)

def check(lab):
    queue = deque()
    for i in range(n):
        for j in range(m):
            if lab[i][j] == 2:
                queue.append([i,j])
    #print(queue)
    while queue:
        i,j = queue.popleft()
        if i-1>=0 and lab[i-1][j] == 0:
            lab[i-1][j] = 2
            queue.append([i-1, j])
        if i+1<n and lab[i+1][j] == 0:
            lab[i+1][j] = 2
            queue.append([i+1, j])
        if j-1>=0 and lab[i][j-1] == 0:
            lab[i][j-1] = 2
            queue.append([i, j-1])
        if j+1<m and lab[i][j+1] == 0:
            lab[i][j+1] = 2
            queue.append([i, j+1])
    #print(lab)

def solution():
    wall = list(itertools.combinations(empty, 3))
    global answer
    for w in wall:
        viruslab = copy.deepcopy(lab)
        count = 0
        for i in range(3):
            viruslab[w[i][0]][w[i][1]] = 1
        #print(lab)
        check(viruslab)
        for i in range(len(viruslab)):
            count += viruslab[i].count(0)
        answer = max(answer, count)
        for i in range(3):
            viruslab[w[i][0]][w[i][1]] = 0

solution()
print(answer)

시도 3

한달이 넘게 지난 오늘 스터디하면서 다시 풀어보았다!

import sys
from collections import deque
from itertools import combinations

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N, M = map(int, input().split())
lab = []
virus_pos = []
empty_pos = []
answer = 0

for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(M):
        if tmp[j] == 0:
            empty_pos.append((i,j))
        elif tmp[j] == 2:
            virus_pos.append((i,j))
    lab.append(tmp)

def in_boundary(x,y):
    if x in range(0, N) and y in range(0,M):
        return True
    else:
        return False

def bfs(lab, virus_pos):
    #모든 바이러스의 위치를 queue에
    queue = deque(virus_pos)
    while queue:
        #각 바이러스에서
        x, y = queue.popleft()
        #상하좌우 검사
        for i in range(4):
            #범위 내에 있고 빈칸이면
            if in_boundary(x+dx[i], y+dy[i]):
                if lab[x+dx[i]][y+dy[i]] == 0:
                    #바이러스 퍼뜨리기 
                    lab[x+dx[i]][y+dy[i]] = 2
                    queue.append((x+dx[i], y+dy[i]))
    count = 0
    for i in range(N):
        count += lab[i].count(0)
    for x,y in empty_pos:
        lab[x][y] = 0
    return count


walls = list(combinations(empty_pos, 3))

for wall in walls:
    for x, y in wall:
        lab[x][y] = 1
    #print(lab)
    #바이러스 퍼뜨리기
    answer = max(answer, bfs(lab, virus_pos))
    for x, y in wall:
        lab[x][y] = 0
print(answer)
profile
Hongik CE

0개의 댓글