본문 바로가기

BFS36

[백준] 13460번 - 구슬 탈출 2 (파이썬) # 구슬 탈출 2 from collections import deque import sys input = sys.stdin.readline # . # 0 R B => 빈칸, 장애물, 구멍, 빨간구슬, 파란구슬 N, M = map(int, input().split()) arr = [] red_x, red_y = 0, 0 blue_x, blue_y = 0, 0 for i in range(N): arr.append(list(input().strip())) for j in range(len(arr[i])): if arr[i][j] == 'R': red_x, red_y = i, j arr[i][j] = '.' elif arr[i][j] == 'B': blue_x, blue_y = i, j arr[i][j] = '.. 2022. 2. 11.
[백준] 13459번 - 구슬 탈출 (파이썬) # 구슬 탈출 from collections import deque import sys input = sys.stdin.readline # . # 0 R B => 빈칸, 장애물, 구멍, 빨간구슬, 파란구슬 N, M = map(int, input().split()) arr = [] red_x, red_y = 0, 0 blue_x, blue_y = 0, 0 for i in range(N): arr.append(list(input().strip())) for j in range(len(arr[i])): if arr[i][j] == 'R': red_x, red_y = i, j arr[i][j] = '.' elif arr[i][j] == 'B': blue_x, blue_y = i, j arr[i][j] = '.'.. 2022. 2. 11.
[백준] 1525번 - 퍼즐 (파이썬) # 퍼즐 from collections import deque N = 3 arr = [] zero_x = 0 zero_y = 0 for i in range(N): arr.append(list(map(int, input().split()))) for j in range(N): if arr[i][j] == 0: zero_x = i zero_y = j dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] visit = dict() def bfs(a, b): global arr q = deque() string = change(arr) if string == '123456780': return '0' q.append((a, b, 0, string)) visit[string] = True while.. 2022. 2. 9.
[백준] 17471번 - 게리맨더링 (파이썬) # 게리멘더링 import sys from collections import deque MAX = sys.maxsize input = sys.stdin.readline N = int(input()) person = [0] + list(map(int, input().split())) arr = [[] for _ in range(N+1)] for i in range(1, N+1): temp = deque(map(int, input().split())) temp.popleft() arr[i] = list(temp) def bfs(area): q = deque() visited = [False] * (N+1) q.append(area[0]) visited[area[0]] = True temp = 0 count .. 2022. 2. 5.
[백준] 1939번 - 중량제한 (파이썬) # 중량제한 import sys from collections import deque MAX = sys.maxsize input = sys.stdin.readline N, M = map(int, input().split()) arr = [[] for _ in range(N+1)] weight = [MAX] * (N+1) for _ in range(M): a, b, cost = map(int, input().split()) arr[a].append((b, cost)) arr[b].append((a, cost)) start_city, arrive_city = map(int, input().split()) def bfs(mid): q = deque() q.append(start_city) visited[sta.. 2022. 2. 4.
[백준] 5427번 - 불 (파이썬) # 불 from collections import deque import sys input = sys.stdin.readline dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] def burn(): for _ in range(len(fire)): x, y = fire.popleft() for k in range(4): nx = x + dx[k] ny = y + dy[k] if 0 2022. 2. 2.
[백준] 2146번 - 다리 만들기 (파이썬) # 다리 만들기 from collections import deque import sys input = sys.stdin.readline MAX = sys.maxsize N = int(input()) arr = [] sea = [] for i in range(N): arr.append(list(map(int, input().split()))) for j in range(N): if arr[i][j] == 0: sea.append((i, j)) dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] result = MAX def bfs(a, b): global result q = deque() q.append((a, b)) visited = [[0] * N for _ in range(N)] w.. 2022. 1. 28.

티스토리툴바