[백준] 14502 연구소

백준 14502번 연구소

그래프 / 완전탐색 / dfs&bfs / 삼성전자 SW 역량테스트

 

 

 

[문제]

 

 

 

 

그래프에 벽을 3개 세우는 모든 경우의 수를 구해야 하므로, 조합이 필요하다.

DFS, BFS, itertools 로 구할 수 있는데 나는 조합 라이브러리인 itertools를 사용해서 구현했다.

 

 

 

 

 

전체 맵의 크기가 8x8 이므로, 벽을 설치할 수 있는 모든 조합의 수는 최악의 경우 64C3이 될 것.

이는 100,000보다도 작은 수 이므로 모든 경우의 수를 고려해도 시간안에 해결 가능하다.

 

 

 

 

[과정]

 

1. graph의 값들을 입력받고 해당값이 2인경우 별도의 리스트(virus_list)에 저장하고 0인경우 해당 인덱스값을 얻기위해 별도의 리스트(map)에 좌표값을 저장

(2차원리스트로 조합 라이브러리를 사용하기 위해 좌표값이 필요하다)

 

2. 조합(combinations)를 사용하여 3개씩 조합을 구함(data_list)

 

3. 조합의 수만큼 반복:

    3-1) 반복할때마다 graph가 필요하므로 깊은복사로 graph복사본(tmp_maps)를 만듬

    3-2) tmp_maps에 벽을 설치하고 2의 좌표에서 virus(dfs)를 실행

    3-3) virus()는 이동 좌표값이 0일때 해당 값을 2로 교체 하여 tmp_maps를 변경해주는 dfs함수

    3-4) 하나의 조합이 끝나면 안전영역의 크기(get_score())를 구하여 최댓값을 갱신

 

 

 

 

 

[소스코드]

 

# 연구소

from itertools import combinations
import copy
import sys
sys.setrecursionlimit(10**7)

# 입력 
n, m = map(int, input().split())
graph = []    # 지도 
maps = []     # 각 값들의 위치 
virus_list = []    # 2의 위치

for i in range(n):
    arr = list(map(int,input().split()))
    for j in range(len(arr)):
        if arr[j] == 2:
            virus_list.append((i,j))
        elif arr[j] == 0:
            maps.append((i,j))
    graph.append(arr)

data_list = list(combinations(maps,3))


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

# 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 tmp_maps[nx][ny] == 0:
                tmp_maps[nx][ny] = 2
                virus(nx,ny)

# 안전 영역의 크기
def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if tmp_maps[i][j] == 0:
                score += 1
    return score

# 조합만큼 반복하며 2의 위치에서 dfs 실행
ans = 0
for data in data_list:
    tmp_maps = copy.deepcopy(graph)
    for x,y in data:
        tmp_maps[x][y] = 1
    for vx, vy in virus_list:
        if tmp_maps[vx][vy] == 2:
            virus(vx,vy)
    ans = max(ans, get_score())
print(ans)

 

 

---

 

 

[통과]