백준 14502 - 파이썬

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

14502번: 연구소

문제 풀이

다른 BFS 문제들은 풀이 방식이 유사했으나 이번 문제는 구현 + BFS 문제이기에 처음 풀어보는 유형이었다. 그래서 30분정도 고민하다가 벽을 어떻게 세워야 할지 모르겠어서 특성 블로그의 글이 아닌 구글링을 통해 다른 사람들의 여러 풀이를 찾아봤다.

 

다른 사람의 풀이를 찾아보면서 벽을 세우는 방법은 완전 탐색으로 세워야 하며, 백트래킹이라는 기법으로 세워야 한다는 것도 알게 되었다. 백트래킹은 처음 접하는 개념이어서 한번 찾아봤는데 이해한 내용은 다음과 같다. 

DFS를 이용하여 조건에 맞지 않으면 그 이전으로 돌아가서 조건에 알맞은 값이 나올때까지 계속 반복하며 탐색하는 것

첫번째 코드는 deepcopy를 이용하여 구현한 것이고, 두번째 코드는 visited 리스트를 만들어 구현한 것이고, 마지막 코드는 <이것이 코딩 테스트다> 라는 책에서 소개된 코드이다.

첫번째 코드

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

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
answer = 0

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

def madeWall(cnt):
  if cnt == 3:
    virus()
    return

  for i in range(n):
    for j in range(m):
      if graph[i][j] == 0:
        graph[i][j] = 1
        madeWall(cnt + 1)
        graph[i][j] = 0

def virus():
  global answer
  copy_graph = copy.deepcopy(graph)
  q = deque()
  for i in range(n):
    for j in range(m):
      if copy_graph[i][j] == 2:
        q.append((i, j))

  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = dx[i] + x
      ny = dy[i] + y
      if 0 <= nx < n and 0 <= ny < m and copy_graph[nx][ny] == 0:
        copy_graph[nx][ny] = 2
        q.append((nx, ny))

  safe_cnt = 0
  for row in copy_graph:
    safe_cnt += row.count(0)
  answer = max(answer, safe_cnt)

madeWall(0)
print(answer)

두번째 코드

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

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

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
cnt = 0

for i in range(n):
  for j in range(m):
    if graph[i][j] == 0:
      cnt += 1

answer = 0

def bfs():
  visited = [[False] * m for _ in range(n)]

  global answer
  result = 0
  q = deque()

  for i in range(n):
    for j in range(m):
      if graph[i][j] == 2:
        visited[i][j] = 1
        q.append((i, j))

  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = dx[i] + x
      ny = dy[i] + y

      if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
        if graph[nx][ny] == 0:
          visited[nx][ny] = True
          result += 1
          q.append((nx, ny))

  answer = max(answer, cnt - result)

def wall_dfs(cnt):
  if cnt == 3:
    bfs()
    return

  for i in range(n):
    for j in range(m):
      if graph[i][j] == 0:
        graph[i][j] = 1
        wall_dfs(cnt + 1)
        graph[i][j] = 0

wall_dfs(0)
print(answer - 3)

이코테

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
temp = [[0] * m for _ in range(n)]

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

result = 0

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)

def get_score():
  score = 0
  for i in range(n):
    for j in range(m):
      if temp[i][j] == 0:
        score += 1

  return score

def dfs(cnt):
  global result
  if cnt == 3:
    for i in range(n):
      for j in range(m):
        temp[i][j] = graph[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 graph[i][j] == 0:
        graph[i][j] = 1
        dfs(cnt + 1)
        graph[i][j] = 0

dfs(0)
print(result)

 

이번 문제에서 새로운 개념들을 접해봤는데 아직 미숙한거 같다. 비슷한 문제들을 풀어보면서 손에 익도록 노력해야 되겠다.