[BOJ1261 알고스팟] BFS (Python)
문제조건 벽이 있으면 뚫고 이동, 벽이 없으면 그냥 이동한다. 핵심개념 가중치(부수는 벽의 개수)는 벽이 있느냐 마느냐에 따라 0이거나 1이다. 가중치가 1이면 deque의 왼쪽, 0이면 deque의 오른쪽을 사용한다. (2개의 큐인 것처럼 활용) 코드 from collections import deque n, m = map(int, input().split()) miro = [list(map(int, input())) for _ in range(m)] check = [[False] * n for _ in range(m)] dist = [[-1] * n for _ in range(m)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 처음 위치 q = deque() q.append..
2019. 10. 7.
[BOJ3055 탈출] BFS (python)
문제조건 물은 1분이 지날 때마다 인접한 곳에 물이 찬다. 단, 돌이거나 비버의 소굴은 물이 차지 않는다. 고슴도치는 물과 돌은 못 간다. 핵심개념 물 차는 시간을 미리 구해놓는다. (토마토 문제 방법으로 구하면 된다.) 위, 아래, 왼쪽, 오른쪽 인접한 곳을 탐색한다. 코드 from collections import deque n, m = map(int, input().split()) a = [list(map(str, input())) for _ in range(n)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 물 차는 시간 먼저 구하기 (토마토 문제랑 동일) # 구하는 김에 고슴도치랑 비버의굴 위치도 구하기 water = [[-1] * m for _ in range(n)]..
2019. 10. 7.
[BOJ 7576 - 토마토] BFS 알고리즘 (Python)
문제조건 하루가 지나면, 익은 토마토(1)의 인접한 토마토가 익는다(0 -> 1). 인접한 것은 아래, 위, 왼쪽, 오른쪽에 해당한다. 토마토가 모두 익는데 걸리는 최소 일수를 구하라. 핵심개념 익은 토마토(1) 여러 개에서 동시에 탐색을 시작하는 꼴이다. 처음에 익은 토마토들을 모두 queue에 넣고 탐색을 시작하자. 코드 from collections import deque import sys from functools import reduce m, n = map(int, input().split()) tomato = [list(map(int, input().split())) for _ in range(n)] days = [[-1] * m for _ in range(n)] dx = [1, -1, 0,..
2019. 10. 6.