백준16946 - 벽 부수고 이동하기 4 (DFS) Python

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

해당 문제는 DFS 알고리즘을 응용하여 해결할 수 있는 문제다.

 

풀이 과정은 다음과 같다.

1. DFS 알고리즘을 활용해, 벽이 아닌 방의 크기를 구해나간다.

이때, 방문여부 처리를 하여 이전에 방문했던 곳을 다시 방문치 않게 하며,

방 번호 변수를 선언하여 각 공간마다 구분할 수 있게 방 번호를 매기고,

DFS 알고리즘 종료 시 리턴되는 방 번호(깊이)와 방 크기를 함께 저장한다.

def solution (data) :
  n,m = map(int, data.pop(0).split())
  arr = [list(map(int, list(x))) for x in data]

  # 방향
  directions = [[-1,0],[0,-1],[1,0],[0,1]]
  # 방문 여부 저장
  visited = [[0 for _ in range(m)] for _ in range(n)]
  # 방 번호 저장
  info = [[0 for _ in range(m)] for _ in range(n)]
  # 방 크기 저장
  roomsSize = {}
  # 방 번호 변수
  roomNum = 0

  for i in range(n) : 
    for j in range(m) :
      if not arr[i][j] and not visited[i][j] : 
        roomNum += 1
        size = DFS(arr, directions, visited, info, roomNum, i,j)
        roomsSize[roomNum] = size

def DFS(arr, directions, visited, info, roomNum, y, x) :
  stack = deque([[x,y]])
  dep = 0
  while stack :
    x,y = stack.pop()
    if visited[y][x] : continue

    visited[y][x] = 1
    info[y][x] = roomNum
    dep += 1

    for [dx,dy] in directions : 
      nx,ny = dx+x, dy+y
      if verify(len(arr[0]), len(arr), nx, ny) and not visited[ny][nx] and not arr[ny][nx] :
        stack.append([nx,ny])

  return dep

# 유효한 위치인지 확인하는 함수
def verify(X,Y,x,y) :
  return 0 <= x < X and 0 <= y < Y

 

2. 벽인 공간에 접근한 뒤, 해당 좌표에서 상하좌우에 있는 좌표가 '벽'이 아닌지와 2차원 배열 내에 존재하는 유효한 좌표인지 확인한다.

유효한 위치라면 앞서 구했던 상하좌우 좌표의 '방 번호'와 '방 번호에 따른 방 크기'를 파악하여 더해나간다.

이때 '벽을 부술 시 공간'은 현재 좌표를 포함하기 때문에, 1에서부터 시작하며 방 번호가 중복되어 사용되지 않게 해야 한다. 

for i in range(n) : 
    for j in range(m) :
      if arr[i][j] :
        # 부순 공간의 기본값
        brokenRoomSize = 1
        # 중복된 방 번호를 사용하지 않기 위한 임시 배열
        usedRoom = []
        for [dx,dy] in directions : 
          nx,ny = dx+j, dy+i
          if verify(len(arr[0]), len(arr), nx, ny) and info[ny][nx] :
            if not info[ny][nx] in usedRoom :
              usedRoom.append(info[ny][nx])
              brokenRoomSize += roomsSize[info[ny][nx]]
        arr[i][j] = brokenRoomSize % 10

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
from collections import deque

def solution (data) :
  n,m = map(int, data.pop(0).split())
  arr = [list(map(int, list(x))) for x in data]

  directions = [[-1,0],[0,-1],[1,0],[0,1]]
  visited = [[0 for _ in range(m)] for _ in range(n)]
  info = [[0 for _ in range(m)] for _ in range(n)]
  roomsSize = {}
  roomNum = 0

  for i in range(n) : 
    for j in range(m) :
      if not arr[i][j] and not visited[i][j] : 
        roomNum += 1
        size = DFS(arr, directions, visited, info, roomNum, i,j)
        roomsSize[roomNum] = size


  for i in range(n) : 
    for j in range(m) :
      if arr[i][j] :
        brokenRoomSize = 1
        usedRoom = []
        for [dx,dy] in directions : 
          nx,ny = dx+j, dy+i
          if verify(len(arr[0]), len(arr), nx, ny) and info[ny][nx] :
            if not info[ny][nx] in usedRoom :
              usedRoom.append(info[ny][nx])
              brokenRoomSize += roomsSize[info[ny][nx]]
        arr[i][j] = brokenRoomSize % 10

  result = list(map(lambda x : ''.join(map(str, x)), arr))
  print('\n'.join(result))

def DFS(arr, directions, visited, info, roomNum, y, x) :
  stack = deque([[x,y]])
  dep = 0
  while stack :
    x,y = stack.pop()
    if visited[y][x] : continue

    visited[y][x] = 1
    info[y][x] = roomNum
    dep += 1

    for [dx,dy] in directions : 
      nx,ny = dx+x, dy+y
      if verify(len(arr[0]), len(arr), nx, ny) and not visited[ny][nx] and not arr[ny][nx] :
        stack.append([nx,ny])

  return dep

def verify(X,Y,x,y) :
  return 0 <= x < X and 0 <= y < Y

solution(input_data)