연구소 (백준 14502_골드4) DFSBFS
메모
n x m
- 0 : 빈칸
- 1 : 벽 (테케에서 없을수도 있음)
- 2 : 바이러스 (많을수도 있음)
바이러스 -> 상하좌우 모두 퍼져나감
반드시 딱 3개의 벽을 추가해야함
3개벽을 추가해서 바이러스(=2)가 퍼질 수 없도록 하고,
안전영역(=벽을 3개 추가해서 막고, 바이러스가 아닌 영역)이 최대가 되는 프로그램
알고리즘 및 방법
- 바이러스 BFS 방식을 활용하는데
- 내가 처음에 생각한 방법
- 일단 2위치(=시작점)를 알아내야 bfs하기 때문에 맨 처음에도 2를 파악하기위한 브루트포스 수행해야함
- 모든 경우의 수마다 BFS돌리는 브루트포스를 해야하나?
- 브루트포스로 => 0인곳만 => i, j, k 돌려가며 3곳에 1을 삽입 (-->x,y라서 for문 6개???=> 큐하나더쓰면될듯?)
- 3개가 됐다면, 2가 있는 위치를 전부 큐에 넣고 bfs (토마토/바이러스처럼)
- 만약 0 not in graph : 실패
- 만약 0 in graph : 성공 -> 개수를 세기 위해 bfs 또 하거나, 브루트포스 count해야함
- 그래프 원상복구 해줘야함
- 문제 풀이 (중요)
- 일단 2위치(=시작점)를 알아내야 bfs하기 때문에
- 브루트포스로 바이러스(2) 위치 저장
- 그리고 모든 빈 공간(0)의 위치도 저장 (~> 벽3개 만들게)
- 일단 2위치(=시작점)를 알아내야 bfs하기 때문에
- 브루트포스 말고 Collections 사용해서 "추가 벽 3개 저장할 수 있는" 모든 경우의수 만듦
- temp graph 만든다 (copy.deepcopy(arr)사용!!)
- temp queue도 만든다 (얘는 걍 deque에 할당하면 됨)
- 모든 경우의 수별로, tmp_graph에 벽(1) 3개 만들고
- 바이러스(2)가 있는 위치를 전부 큐에 넣고 bfs (토마토/바이러스처럼)
- bfs를 돌면 바이러스가 전파됨
- bfs 끝나고 0인 것들 전부 체크(sub_num++)
- bfs의 return = sub_num
- 그래프 원상복구 해줘야함(딥카피!)
- bfs결과물을 리스트에 모두 저장
- 정답 : max(bfs 결과물들)
동빈나 해설
- 이 문제는 벽을 3개 설치하는 모든 경우의 수를 다 계산해야함
- 전체 맵 크기가 최대 8 * 8이므로,
- 모든 조합의 수는 최악의 경우(바이러스가 하나도 없을 때)
- 64C3 이 된다.
- 이는 100,000보다 작은 수이므로, O(N^3)도 가능(?)하다
설마 바이러스 없는 경우가 있을까????? -> 그런 경우는 없었다^^
솔루션 코드 - 내가 푼
- 한번에 풀었다 다행히
- 그래프 딥카피랑
- 큐 딥카피 만 주의하면 한번에 풀었음
from collections import deque
from itertools import combinations
import copy # 깊은복사 : copy.deepcopy()
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
main_graph = [list(map(int, input().split())) for _ in range(n)]
graph = copy.deepcopy(main_graph)
q = []
zero = []
answer = []
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
# bfs 구현
def bfs(que, graph):
sub_num = 0 # 0의 개수 체크
# 바이러스 이동
while que:
y, x = map(int, que.popleft())
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if 0<=ny and ny<n and 0<=nx and nx<m and graph[ny][nx] == 0:
graph[ny][nx] = 2
que.append((ny, nx))
# 해당 bfs가 끝났으면 0의 개수 체크
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
sub_num += 1
return sub_num
# 바이러스 위치를 저장하자(bfs 시작용 위치 저장)
for i in range(n):
for j in range(m):
if graph[i][j] == 2:
q.append((i,j))
elif graph[i][j] == 0:
zero.append((i,j))
# 브루트포스로 0인 곳만 3개의 벽을 세워보자 (= walls[0] [1] [2]가 벽)
for walls in combinations(zero, 3): # 중복필요없어서 combinations
# (중요) 그래프 원상복구 -> 깊은복사!
graph = copy.deepcopy(main_graph)
que = deque(q)
y1, x1 = map(int, walls[0])
y2, x2 = map(int, walls[1])
y3, x3 = map(int, walls[2])
graph[y1][x1] = 1
graph[y2][x2] = 1
graph[y3][x3] = 1
# 이제 bfs를 돌려 -> graph를 바이러스로 물들인다
# bfs 끝나면 bfs 안에서 0이 존재하는지 브루트포스로 개수 센다 -> return 개수 -> ans.append
answer.append(bfs(copy.deepcopy(que), graph))
print(max(answer))
솔루션 코드 - 동빈나
-
링크 : https://github.com/ndb796/python-for-coding-test/blob/master/13/2.py
-
pypy로 제출하라고 함
# BOJ에서는 [언어]를 PyPy3로 설정하여 제출해주세요.
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())))
# 4가지 이동 방향에 대한 리스트
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
# 울타리가 3개 설치된 경우
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)- cpp
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[8][8]; // 초기 맵 배열
int temp[8][8]; // 벽을 설치한 뒤의 맵 배열
// 4가지 이동 방향에 대한 배열
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int result;
// 깊이 우선 탐색(DFS)을 이용해 각 바이러스가 사방으로 퍼지도록 하기
void virus(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 상, 하, 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
if (temp[nx][ny] == 0) {
// 해당 위치에 바이러스 배치하고, 다시 재귀적으로 수행
temp[nx][ny] = 2;
virus(nx, ny);
}
}
}
}
// 현재 맵에서 안전 영역의 크기 계산하는 메서드
int getScore() {
int score = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (temp[i][j] == 0) {
score += 1;
}
}
}
return score;
}
// 깊이 우선 탐색(DFS)을 이용해 울타리를 설치하면서, 매 번 안전 영역의 크기 계산
void dfs(int count) {
// 울타리가 3개 설치된 경우
if (count == 3) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp[i][j] = arr[i][j];
}
}
// 각 바이러스의 위치에서 전파 진행
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (temp[i][j] == 2) {
virus(i, j);
}
}
}
// 안전 영역의 최대값 계산
result = max(result, getScore());
return;
}
// 빈 공간에 울타리를 설치
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
arr[i][j] = 1;
count += 1;
dfs(count);
arr[i][j] = 0;
count -= 1;
}
}
}
}
int main(void) {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
}
}
dfs(0);
cout << result << '\n';
}
Do My Best