[이코테] DFS - 연구소

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

삼성전자 SW 역량테스트의 문제로 백준에도 실려있으니 문제 설명은 하단의 링크를 참조하자.

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

14502번: 연구소

사고과정

• DFS로 풀어야 한다고 생각했지만 접근조차 못했다. 그래서 문제풀이를 보았음.
• 크게 4가지 핵심 아이디어
  1. 주어진 정보를 담는 2차원 배열 하나, 주어진 정보 + 벽 3개를 설치한 후의 2차원 배열 하나 2가지 배열을 운영
  2. 3개 벽을 쌓을 수 있는 모든 경우의 수를 2중 반복문 + DFS를 활용해 탐색
  3. 바이러스(2)가 상,하,좌,우로 전파할 수 있는 영역을 DFS 탐색해야 함
  4. 2번을 수행한 후 안전영역(0인 값)을 계산해야 함
• 1, 3, 4 단계는 이해했는데, 2번 단계는 여전히 이해하지 못하고 있다. 계속 풀어보면 알 수 있을까? 하나씩 코드를 출력해보아도 모르겠다. 책 깃헙 이슈에 남겨도 답변이 안달림... 대체 3가지 벽을 설치하는 경우의 수를 2중 반복문과 DFS를 활용한 코드는 어떻게 동작하는 건가? 답변 아시는 분... 댓글 좀 달아주세요..

풀이(스스로 풀지 못함)

한 50번은 풀어보면 이해가 되지 않을까..?

import sys

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())))

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

result = 0
# 1. 바이러스가 전파시키는 DFS 함수
def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                virus(nx, ny)

# 2. 안전영역 계산하는 함수
def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score

# 3. 벽 설치하는 모든 경우의 수 탐색하면서 안전영역 계산
def dfs(count):
    global result
    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)