2022-08-10 TIL

 

☝ 연속된 숫자를 리스트 형태로 받아오는 법

• '101010'과 같은 숫자를 [1, 0, 1, 0, 1, 0]과 같은 리스트로 변환하는 법

#import sys 사용안하는 경우
array = []
for i in range(n) :
  array.append(list(map(int, input())))
  
#import sys 사용하는 경우
import sys
input = sys.stdin.readline

array = []
for i in range(n) :
  array.append(list(map(int, input().strip())))

 

 

☝ bfs를 동시에 하는 법

• 백준 7576번 문제의 경우 bfs를 동시에 해야함
• 그래프를 보자

7576 예제 그래프

• 위의 그래프에서 (0,0)과 (3, 5) 그래프의 1은 동시에 bfs 를 수행해야 한다.
• 이런 경우 queue에 자료 구조를 담아 놓고 bfs를 돌리면 동시에 수행된다.
• 다음 코드로 일단 queue에 1의 좌표를 담아 둔다.

m, n = map(int, input().split())
graph = []
q = deque()
for i in range(n) :
  graph.append(list(map(int, input().split())))

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

• 이후 bfs를 돌려 동시에 bfs를 수행하게 한다.

def bfs() :
  while q :
    a, b = q.popleft()

    for i in range(4) :
      nx = a + dx[i]
      ny = b + dy[i]
  
      if not (0 <= nx < n) or not (0 <= ny < m) :
        continue
      if graph[nx][ny] == 0 :
        graph[nx][ny] = graph[a][b] + 1
        q.append((nx, ny))

bfs()

 

 

 

☝ 3차원 배열을 사용해서 벽 부수기

• 백준 2206번 문제

 

• 3차원 배열을 사용해 벽을 부순 경우와 벽을 부수지 않은 경우로 나누어 카운트를 할 수 있다.

import sys
from collections import deque

input = sys.stdin.readline
q = deque()
n, m = map(int, input().split())
graph=[]

visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
visited[0][0][0] = 1

for i in range(n):
    graph.append(list(map(int, input().strip())))

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

def bfs(x, y, z):
    queue = deque()
    queue.append((x, y, z))

    while queue:
        a, b, c = queue.popleft()
        if a == n - 1 and b == m - 1:
            return visited[a][b][c]
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 1 and c == 0 :
                visited[nx][ny][1] = visited[a][b][0] + 1
                queue.append((nx, ny, 1))
            elif graph[nx][ny] == 0 and visited[nx][ny][c] == 0:
                visited[nx][ny][c] = visited[a][b][c] + 1
                queue.append((nx, ny, c))
    return -1

print(bfs(0, 0, 0))