너비우선탐색

문제 접근 [백준 알고리즘] 7576번: 토마토 (Python / 파이썬) 문제 접근 헷갈렸던 문제이다. bfs를 사용하는데 시작 지점이 여러개다. 단순히 queue 사이클이 몇번 돌아갔는지 체크하면 당연히 더 큰 값이 나와 틀릴 것이기 때문에 한 사이클에 몇개의 요소가 gyujh.tistory.com 이전에 풀었던 7576번 토마토 문제의 3차원 버전이다. 이때 풀었던 방법과 다르게, 큐에 새로운 익은 토마토를 넣을 때 그 값에 이전 토마토 값 + 1 을 할당하여 날짜 계산을 더 쉽게 처리했다. 주의할 점으로는 시작점이 되는 토마토들이 1의 값을 가지고 있으므로, 위처럼 날짜 계산을 한다면 이 시작 값들은 0이 되거나 마지막에 최댓값을 구하고 1을 빼줘야 한다. 1의 의미는 하루가 지났음의 의미인데 ..

문제 접근 최단 경로를 구하는 문제이므로 bfs가 적합하다. n * m 행렬이 주어지고, 시작점이 정해져 있기에 생각보다 간단한 문제라고 생각했다. 벽(1)을 한 번만 부술 수 있으므로, 모든 벽들을 하나씩 부숴보고 bfs를 각각 돌려 최솟값을 구하면 된다고 생각했지만, n , m

문제 접근 deepcopy로 matrix를 하나 복사해서 색약용은 G -> R를 같은 문자로 만들어준다. 각각 순회하며 일반용은 값이 R, G, B일 때, 색약용은 R, B일 때 bfs를 호출한다. bfs 안에서는 방문한 곳을 X로 바꿔주고 탐색이 끝나고 1을 리턴한다. bfs가 실행된 횟수를 카운트하면 영역의 수가 된다. 정답 코드 # 10026번: 적록색약 import sys import copy from collections import deque def bfs(matrix, x, y, color): queue = deque() queue.append((x, y)) matrix[x][y] = 'X' dx, dy = [1, 0, 0, -1], [0, 1, -1, 0] while queue: cur =..

문제 접근 간단한 bfs 너비우선탐색 문제이다. 1) 밭을 돌면서 1을 발견할 때마다 bfs를 실행한다. 2) bfs 안에서, 이어진 1인 곳들을 방문하며 0으로 바꿔놓는다. 3) bfs가 끝날 때마다 정답에 1을 더한다. 정답 코드 #1012번: 유기농 배추 import sys from collections import deque def bfs(field, x, y): queue = deque() queue.append((x, y)) while queue: cur = queue.popleft() dx, dy = [0, 1, -1, 0], [1, 0, 0, -1] for i in range(4): nx, ny = cur[0] + dx[i], cur[1] + dy[i] if 0

문제 접근 헷갈렸던 문제이다. bfs를 사용하는데 시작 지점이 여러개다. 단순히 queue 사이클이 몇번 돌아갔는지 체크하면 당연히 더 큰 값이 나와 틀릴 것이기 때문에 한 사이클에 몇개의 요소가 큐에 들어갔고, 그것들에 의해서는 몇개가 큐에 추가되었는지 체크해야 한다. temp, count, answer 세 개의 변수를 사용해서 특정 주기에 초기화시켜서 풀었다. 예를 들어, 시작점(1)이 2개, 그 시작점으로 인해 생긴 것(2)이 2개, (2)에 의해 3개가 큐에 들어갔다면 날짜 카운트를 bfs 반복 주기의 2번째, 4번째(2+2), 7번째(4+3)마다 해줘야 한다. 내가 짠 대로 하면 마지막 토마토까지 다 익고 나서 그 토마토가 영향을 주는 시간까지 고려되기 때문에 -1을 해준다. 불가 판단(-1 ..