[Python] 백준 2665 미로 만들기, 백준 1261 알고스팟

1. 문제 - 백준 2665 미로 만들기

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

 

💡알고리즘 - 0-1 BFS

• 0-1 BFS란 가중치가 0, 1만 존재하는 그래프에서의 최단 거리를 구하는 알고리즘이다.
• 가중치가 0인 경로를 우선적으로 탐색하기 위해 이 경우 deque에 appendleft하여 front에 두고, 가중치가 1인 경로는 가중치가 0인 경로보다 후순위이므로 deque에 append하여 back에 둔다.
• 흰방으로 이동할때, 검은 방에서 흰 방으로 바꾸지 않아도 되므로 가중치 0
  검은 방으로 이동할 때, 검은 방에서 흰 방으로 바꾸어야 하므로 가중치 1로 두고 알고리즘을 짠다.
• 자세한 알고리즘 설명 관련해서는 https://velog.io/@iamdudumon/0-1-BFS 참고

 

❌ 시간초과 풀이

from collections import deque
from itertools import combinations
import copy

# 검은 방은 들어갈 수 없고, 서로 인접한 두 개의 흰방 사이에는 문에 있어서 지나다닐 수 있다 -> 인접하게 이동할 수 있는 offset 배열
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
blacks = []

n = int(input())
board = []
for i in range(n):
  board.append(list(map(int, input())))
  for j in range(n):
    if board[i][j] == 0:
      blacks.append((i, j))

def bfs(board):
  visited = [[False] * n for _ in range(n)]
  q = deque([(0, 0)])
  visited[0][0] = True

  while q:
    x, y = q.popleft()

    # 끝방까지 도달할 수 있음
    if x == n-1 and y == n-1:
      return True
      
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

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

  return False     # 도달할 수 없음

if bfs(board):  # 검은방을 하나도 흰방으로 바꾸지 않은 지금 끝방에 돌아갈 수 있다면 정답은 0이다.
  print(0)
  exit()
  
for num in range(1, len(blacks)+1):
  for combi in list(combinations(blacks, num)):
    board2 = copy.deepcopy(board)
    for x, y in combi:
      board2[x][y] = 1
    if bfs(board2):
      print(num)
      exit()

- 처음에 combinations를 통해 모든 검정색 칸을 세서, 모든 조합을 구해 완전 탐색을 하려고 했다.

- 그런데 n의 범위가 1<=n<=50 이고, 적게 잡아 검은 칸의 갯수가 30개라고 했을 때에도 2^30 = 10억이므로 시간초과가 발생한다.

- 따라서 단순히 BFS를 모든 검정색 칸들에 대해 n개 만큼 칠한 다음 돌리는 이와 같은 코드는 시간초과가 발생한다.

✅ 0-1 BFS 풀이

from collections import deque

# 검은 방은 들어갈 수 없고, 서로 인접한 두 개의 흰방 사이에는 문에 있어서 지나다닐 수 있다 -> 인접하게 이동할 수 있는 offset 배열
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n = int(input())
board = []
for _ in range(n):
  board.append(list(map(int, input())))

def bfs():
  visited = [[-1] * n for _ in range(n)]    
  # 방문 여부와 검정색을 흰색으로 바꾼 갯수를 저장할 nxn 배열
  q = deque([(0, 0)])
  visited[0][0] = 0

  while q:
    x, y = q.popleft()

    # 끝방까지 도달할 수 있음
    if x == n-1 and y == n-1:
      return visited[x][y]
      
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0<=nx<n and 0<=ny<n and visited[nx][ny] == -1:
        if board[nx][ny] == 1:   # 흰색 방인 경우 가중치 0 -> appendleft
            q.appendleft((nx, ny))
            visited[nx][ny] = visited[x][y]
        else:    # 검은색 방인 경우 부숴야 하니까 가중치 1 -> append, 흰색으로 바꾸는 경우의 수 갱신
            q.append((nx, ny))
            visited[nx][ny] = visited[x][y] + 1

print(bfs())

 

- visited: 방문 여부와 검은색에서 흰색으로 바꾼 경우의 수를 저장할 배열이다.

- 흰색 방인 경우, 즉 board[nx][ny] == 1 일 경우 그 이전의 검은색에서 흰색으로 바꾼 경우의 수를 저장하며 appendleft를 통해 deque의 front에 추가한다.

- 검은색 방의 경우, 즉 board[nx][ny] == 0 일 경우 그 이전의 검은색에서 흰색으로 바꾼 경우의 수에 + 1을 통해 갱신하며, append를 통해 deque의 back에 추가한다.

 

2. 문제 - 백준 1261 알고스팟

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

관련해서 비슷한 문제인 1261 알고스팟 문제도 풀어보았다.

 

💡알고리즘 - 0-1 BFS

• 0-1 BFS란 가중치가 0, 1만 존재하는 그래프에서의 최단 거리를 구하는 알고리즘이다.
• 빈방으로 이동할 때, 벽을 부수지 않아도 되므로 가중치 0
  벽으로 이동할 때, 벽을 부숴야 이동가능하므로 가중치 1로 두고 알고리즘 짜기

✅ 풀이

from collections import deque

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

m, n = map(int, input().split())
board = []
for _ in range(n):
  board.append(list(map(int, input())))

def bfs():
  visited = [[-1] * m for _ in range(n)]    
  # 방문 여부와 검정색을 흰색으로 바꾼 갯수를 저장할 nxn 배열
  q = deque([(0, 0)])
  visited[0][0] = 0

  while q:
    x, y = q.popleft()

    # 끝방까지 도달할 수 있음
    if x == n-1 and y == m-1:
      return visited[x][y]
      
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0<=nx<n and 0<=ny<m and visited[nx][ny] == -1:
        if board[nx][ny] == 0:
            q.appendleft((nx, ny))
            visited[nx][ny] = visited[x][y]
        else:
            q.append((nx, ny))
            visited[nx][ny] = visited[x][y] + 1

print(bfs())