BFS

[백준] 1260. DFS와 BFS - 파이썬

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 기본적인 DFS, BFS 구현 문제. dictionary를 사용한다면, 없는 key에 접근하지 않도록 유의할 것. 예외처리를 하지 않고 제출했다가, 런타임 에러(keyError)가 남. line 30~32, 49~51과 같이 정점에 연결된 간선이 없을 때를 예외처리 해 주면 된다. 아마 정점이 딱 하나만 들어왔을 때 Error가 났을 듯. from col..

[백준] 1012. 유기농 배추 - 파이썬

https://www.acmicpc.net/problem/1012 풀이 [백준 3197 - 백조의 호수], [백준 7569 - 토마토] 문제와 유사했던 문제. 마찬가지로, BFS를 이용해 풀이. 배추밭을 2차원 배열로 초기화, 이후 입력된 배추의 좌표를 가지고 2차원배열에 적용. 매 반복마다, 배추가 없는 지 확인. 배추가 있다면, 제일 먼저 발견된 배추를 Queue에 넣고, 먹어치워진 배추의 상하좌우를 탐색하며 BFS를 이용해 탐색을 진행. 인접한 모든 배추를 처리하고 나서, 다시 다음 반복을 진행~ 복잡한 건 없어서 주석 이외 부가 설명은 필요하지 않은 듯.. ^ㅁ^ from collections import deque test_case_cnt = int(input()) # 결과값 저장 worms =..

[백준] 7569. 토마토 - 파이썬

https://www.acmicpc.net/problem/7569 풀이 [백준 3197 - 백조의 호수] 문제와 상당히 유사했던 문제. BFS를 이용해 풀이함. 주의할 점은, 토마토를 익히는 과정에서 한 번 익혀지고, queue에 들어간 토마토는 값이 이미 1이 되었기 때문에, visited나 queue에 이미 존재하는 지 확인할 필요가 없음. in 이나 not in 연산자는 O(N) 의 time complexity를 가지므로, for나 while문 안에서 남발했다가는 그대로 시간초과가 되기 쉽다. [백준 3197 - 백조의 호수] 보다 쉬웠던 점은, 토마토가 다 익었는지 확인하는 과정을 Brute-Force로 처리해도 되었음. 그러나 3차원 배열을 써야 하므로 index의 순서가 바뀌지는 않았는지 항상..