[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.
[BOJ 2667 - 단지번호붙이기] BFS (Python)
문제 조건 위, 아래, 왼쪽, 오른쪽에 집이 있는지 탐색 쭈욱 이어진 곳은 하나의 단지로 세팅 (연결요소 개념) 핵심개념 위, 아래, 왼쪽, 오른쪽 이동을 위한 배열을 만든다. 이동을 하되, 범위를 벗어났는지 아닌지도 체크한다. 모든 정점을 한번씩 시작점으로 하여 탐색한다. 2차원 배열 활용하는 법을 익힌다. (생성, 입력받기, 1차원배열로 만들기 등) 문제풀이 (BFS) 재귀 없이 deque 활용하기 from collections import deque from collections import Counter from functools import reduce # 입력받기 n = int(input()) # 지도 입력받기 (2차원) a = [list(map(int,list(input()))) for _ ..
2019. 10. 3.