[Python, JAVA] 14502 연구소 - DFS/BFS, Brute Force, Back Tracking, 완전 탐색

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

14502번: 연구소

언젠가 알고리즘 스터디에서 풀었어야 했던 문제였지만 실력 부족으로 (?) 풀지 못했었다.

새로이 알고리즘 공부를 시작했으니 한번 풀어보기로 하겠다.

 

맨 처음 위 문제를 두가지 task로 나누어 보았다.

1. "벽 3개" 세우기

2. "안전 지대" 개수 세기

사실 느낌이 오다시피, 위와 같은 그래프를 이용하는 문제는 보통 많은 경우에 BFS, DFS문제이다.

 

""" # 왕 사담

사실 고백하자면 나는 큐를 별로 좋아하지 않는다.

이유는 여러 가지가 있는데 먼저 Queue를 사용할 때는 library를 import해야 하는 귀찮음이 있고 따로 선언도 해야 하고,

재귀를 이용하는 DFS와 다르게 넣었다 뺐다 해야되고... 한 단계 더 귀찮은 일을 해야한다는 고정관념(?)이 있는 것 같다.

사실 유명한 BFS, DFS 문제들은 꼭 Queue를 사용해야 하는 경우가 아니면 거의 다 DFS를 이용했다.

그렇지만 아무래도 BFS를 사용해야만 하는 경우도 있으니,

일단 익숙한 python으로는 DFS를 사용하고, 익숙하지 않은 java는 BFS를 사용함으로써

나한테만 매운 알고리즘 풀이를 해보겠다. ㅎ...Queue도 써봐야 늘지... 라는 생각이 든다. 부끄럽지만

어짜피 내 티스토리는 나만 보기 때문에 아무말 대잔치를 해도 괜찮다... 헿 누가 보면 부끄럽다.

이 글을 작성하는 시간은 오전 2시43분이다.  SSAFY를 해도 주말에는 올빼미로 돌아가는 나...

그렇지만 새벽 올빼미 아침 일찍새가 된다.... 

"""

여기서는 벽을 세우고 안전 지대 개수를 세어야 한다.

안전 지대 개수를 세려면 오염된(?) 부분을 바꾸어 주어야 하는데, 이 때 BFS나 DFS를 활용하면 될 것 같다.

 

import copy
from sys import stdin
 
N, M = map(int, stdin.readline().split())
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
arr = []
virus = []
result = 0
 
#입력을 토대로 그래프를 그려보세
for i in range(N):
    arr.append(list(map(int, stdin.readline().split())))
 
for i in range(N):
    for j in range(M):
        if arr[i][j] ==2:
            virus.append([i, j])
 
def wall(start, cnt):
    global result
    if cnt==3: # 벽 3개를 모두 채웠을 때
        result_arr = copy.deepcopy(arr) #벽 3개를 채운 그래프를 저장해둔다고 생각.
        for v in virus:
            i, j = v[0], v[1]
            dfs(i, j, result_arr) # DFS를 돌려보는거지..
        safe = sum(k.count(0) for k in result_arr) #벽 3개 채운 그래프에서 0 개수 찾기.
        result = max(result, safe) # safe 저장해놓는거지.
        return True # 어짜피 result는 global이다.
 
    else: # 벽 3개를 모두 채우지 못했을 때
        for i in range(start, N*M): #0에서 시작
            x = i//M
            y = i%M
            if arr[x][y] ==0: # 0으로 채워진 공간은 벽을 세울 수 있는 공간이다.
                arr[x][y] =1 # 벽을 한번 세워보고
                wall(i, cnt+1) #돌려보는거지
                arr[x][y]=0 # 다시 돌려놓는 것을 잊지 말자."""
 
def dfs(x, y, arr):
    if arr[x][y] ==2:
        for i in range(4):
            n_x = x + dx[i]
            n_y = y + dy[i]
            if 0<= n_x <N and 0<= n_y < M:
                if arr[n_x][n_y] ==0:
                    arr[n_x][n_y] =2
                    dfs(n_x, n_y, arr)
 
wall(0, 0)
print(result)

일단 맞춘 코드를 넣어본다. 근데 별로 맘에 안든다. 다음에 다시 짜보겠다.