너비 우선 탐색(BFS)은 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 먼저 탐색하는 방법이다.
가까운 정점을 전부 저장해놓고 순서대로 방문해야 하기 때문에 스택으로는 구현이 어렵기에 큐(Queue)를 사용한다.
최단거리를 구하는 문제에 많이 사용되는 알고리즘이다. 아래 코드는 BFS코드 예시이다.
BFS 경로 탐색(인접 리스트, 1260번 DFS와 BFS)
from collections import deque
def bfs(start):
queue = deque([start])
while queue:
node = queue.popleft()
print(node, end=' ')
check[node] = 1
for n in sorted(li[node]):
if check[n] == 0:
queue.append(n)
check[n] = 1
N, M, V = map(int, input().split())
li = [[] for _ in range(N+1)]
for _ in range(M):
a, b = map(int, input().split())
li[a].append(b)
li[b].append(a)
check = [0]*(N+1)
bfs(V)
BFS 문제 풀이(인접 행렬, 1012번 유기농 배추)
from collections import deque
def bfs(y, x):
queue = deque()
queue.append((y, x))
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
y, x = queue.popleft()
for dy, dx in d:
Y, X = y+dy, x+dx
if (0 <= Y < N) and (0 <= X < M) and graph[Y][X] == 1:
queue.append((Y, X))
graph[Y][X] = 0
for case in range(int(input())):
M, N, K = map(int, input().split())
graph = [[0]*M for _ in range(N)]
for _ in range(K):
x, y = map(int, input().split())
graph[y][x] = 1
res = 0
for i in range(N):
for j in range(M):
if graph[i][j] == 1:
graph[i][j] = 0
bfs(i, j)
res += 1
print(res)
백준 알고리즘 문제 풀이)
백준 알고리즘 1012번 유기농 배추(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(10000) def dfs(y, x): graph[y][x] = 0 d = [(-1, 0), (1, 0), (0, -1), (0, 1)] for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < N)..
jinho-study.tistory.com
백준 알고리즘 1260번 DFS와 BFS(python)
기본적인 DFS & BFS 문제이다. from collections import deque def dfs(node): if check[node] == 0: print(node, end=' ') check[node] = 1 for n in sorted(li[node]): dfs(n) def bfs(start): queue = deque([s..
jinho-study.tistory.com
백준 알고리즘 7562번 나이트의 이동(python)
최단경로를 찾아야 되는 기본적인 BFS 문제이다. bfs 함수에서 반복문 4번(위, 아래, 오른쪽, 왼쪽) 돌아가던걸 나이트의 이동경로에 맞게 8번 돌도록 바꿔주면 끝이다. from collections import deque def b
jinho-study.tistory.com
백준 알고리즘 2178번 미로 탐색(python)
최단경로를 찾아야 되는 기본적인 BFS 문제이다. from collections import deque def bfs(): queue = deque() queue.append((0, 0)) d = [(0, 1), (0, -1), (1, 0), (-1, 0)] while queue: y, x = queue.popleft..
jinho-study.tistory.com
백준 알고리즘 2606번 바이러스(python)
기본적인 DFS & BFS 문제이다. 양방향임 구조임에 주의하자. 처음에 단방향으로 만들어 놓고 풀려해서 왜 틀렸는지 한참을 찾았다. DFS 풀이 def dfs(node): if check[node] == 0: check[node] = 1 for t in graph..
jinho-study.tistory.com
백준 알고리즘 2667번 단지번호붙이기(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 def dfs(y, x, cnt): graph[y][x] = 0 d = [(-1, 0), (0, 1), (1, 0), (0, -1)] for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < N) and (0 <= X < N) and graph[Y][X] =..
jinho-study.tistory.com
백준 알고리즘 1697번 숨바꼭질(python)
BFS 문제이다. 인접 행렬, 인접 리스트가 구조가 아닌, 1차원 리스트 구조로 BFS를 구현해주면 된다. from collections import deque def bfs(N, K): queue = deque([N]) while queue: node = queue.popleft() if..
jinho-study.tistory.com
백준 알고리즘 1926번 그림(python)
DFS & BFS 문제이다. BFS로는 쉽게 통과했는데 DFS에서 계속 메모리 초과가 나온다. 한 시간 동안 해봤는데 해결하지 못했고, 내린 결론은 BFS로 풀 수 있는 문제는 BFS로 풀어야겠다는 점이다ㅜ DFS는 B
jinho-study.tistory.com
백준 알고리즘 1743번 음식물 피하기(python)
DFS & BFS 문제이다. BFS 풀이 from collections import deque def bfs(i, j): queue = deque() queue.append((i, j)) d = [(-1, 0), (1, 0), (0, -1), (0, 1)] cnt = 1 while queue: y, x = queue.popleft() for..
jinho-study.tistory.com
백준 알고리즘 2468번 안전 영역(python)
DFS & BFS 문제이다. BFS는 큐에 넣을 때 방문 표시를 해줘야 된다는 점을 항상 주의해야겠다. 큐에서 뺀 뒤에 하면 같은 좌표가 중복으로 큐에 들어가는 것이 반복된다. DFS 풀이 import sys from copy impor
jinho-study.tistory.com
백준 알고리즘 2583번 영역 구하기(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(10000) def dfs(y, x, cnt): graph[y][x] = 1 for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < M) and (0 <= X < N) and graph[Y][X]..
jinho-study.tistory.com
백준 알고리즘 4963번 섬의 개수(python)
DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(10000) def dfs(y, x): graph[y][x] = 0 for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < h) and (0 <= X < w) and graph[Y][X] == 1: dfs(Y, X..
jinho-study.tistory.com
백준 알고리즘 11724번 연결 요소의 개수(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(10000) def dfs(node): check[node] = 1 for n in graph[node]: if check[n] == 0: dfs(n) N, M = map(int, sys.stdin.readline().split..
jinho-study.tistory.com
백준 알고리즘 10026번 적록색약(python)
DFS & BFS 문제이다. 나름 짧게 잘 구현한 것 같다. 이제 좀 DFS, BFS에 익숙해진 것 같다!! DFS 풀이 import sys from copy import deepcopy sys.setrecursionlimit(10000) def dfs(y, x, color): t[y][x] = '0'..
jinho-study.tistory.com
백준 알고리즘 11725번 트리의 부모 찾기(python)
트리 & DFS & BFS 문제이다. 시간 초과를 매우 조심해야 되는 문제다. 처음에 방문 체크 리스트를 N-2번 생성하고 순서대로 체크하도록 구현했어서 그런지 시간 초과가 엄청 나왔다. DFS 풀이 import sys
jinho-study.tistory.com
백준 알고리즘 2644번 촌수계산(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(300000) def dfs(node): for n in graph[node]: if check[n] == 0: check[n] = check[node]+1 dfs(n) n = int(input()) graph = [[] for..
jinho-study.tistory.com
백준 알고리즘 11559번 Puyo Puyo(python)
구현 & DFS & BFS 문제이다. 기업 코딩 테스트에서 나올 것 같은 문제인데 참 재밌게 푼 것 같다. 1. 터트릴 뿌요가 있는지 확인하는 함수(같은 색깔의 뿌요가 4개 이상 뭉쳐 있는지 확인) 2. 뿌요를
jinho-study.tistory.com
백준 알고리즘 1389번 케빈 베이컨의 6단계 법칙(python)
BFS 문제이다. res.append(sum(check)-N)이 포인트인 것 같다. from collections import deque def bfs(node): queue = deque() queue.append(node) while queue: node = queue.popleft() for n in grpah[node]: i..
jinho-study.tistory.com
백준 알고리즘 2589번 보물섬(python)
브루트포스 알고리즘 & BFS 문제이다. 처음에 지도의 크기가 1이나 2같이 작을 경우를 고려하지 못해서 많이 틀렸다. 입력을 받을 때 먼저 처리를 해서 -1, 0으로 이루어진 지도를 생성해서 나중에
jinho-study.tistory.com
다시 풀자_백준 알고리즘 9205번 맥주 마시면서 걸어가기(python)
BFS & DFS 문제이다. 인접리스트를 행렬 형식으로 구현해서 그래프를 생성하면 쉽게 풀 수 있다. 이걸 생각못해서 1시간 넘게 뻘짓을 했다. BFS 풀이 from collections import deque def make_graph(): for i in r..
jinho-study.tistory.com
백준 알고리즘 5567번 결혼식(python)
구현 & BFS 문제이다. 거리가 2 이상 3 이하인 노드의 개수를 출력해주면 된다. from collections import deque def bfs(node): queue = deque() queue.append(node) while queue: node = queue.popleft() for n i..
jinho-study.tistory.com
백준 알고리즘 3184번 양(python)
BFS 문제이다. bfs탐색으로 각 울타리 영역의 양과, 늑대('o'와 'v')의 수를 센 후에, 각 울타리당 양의 수가 늑대보다 많으면 늑대를 0으로, 아니면 양을 0으로 바꿔주고 그 총합을 출력해주면 된다.
jinho-study.tistory.com
백준 알고리즘 16956번 늑대와 양(python)
기본적인 BFS 문제이다. 양과 늑대가 인접해있으면 막을 수가 없으므로 0을 출력해주고, 인접한 경우가 없다면 늑대를 가둬버리고 결과를 출력해주면 된다. from collections import deque def bfs(y, x): for
jinho-study.tistory.com
백준 알고리즘 16953번 A → B(python)
그리디 알고리즘 & BFS 문제이다. from collections import deque def bfs(A, B): cnt = 1 queue = deque() queue.append((A, cnt)) while queue: node, cnt = queue.popleft() if node == B: return cnt if node*..
jinho-study.tistory.com
백준 알고리즘 6118번 숨바꼭질(python)
기본적인 BFS 문제이다. from collections import deque def bfs(node): q = deque() q.append(node) check[node] = 1 while q: node = q.popleft() for n in graph[node]: if check[n] == 0: check[n] = check[no..
jinho-study.tistory.com
백준 알고리즘 18352번 특정 거리의 도시 찾기(python)
기본적인 BFS 문제이다. from collections import deque def bfs(node): q = deque() q.append(node) check[node] = 0 while q: node = q.popleft() for n in graph[node]: if check[n] == -1: check[n] = check[n..
jinho-study.tistory.com
백준 알고리즘 16948번 데스 나이트(python)
기본적인 BFS 문제이다. from collections import deque def bfs(y, x): q = deque() q.append((y, x)) graph[y][x] = 0 while q: y, x = q.popleft() for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < N) and (0..
jinho-study.tistory.com
백준 알고리즘 16928번 뱀과 사다리 게임(python)
기본적인 BFS 문제이다. if check[t] == -1 or check[t] > graph[n]+1 부분이 핵심인 것 같다. from collections import deque def bfs(node): q = deque() q.append(node) check[node] = 0 while q: node = q.pop..
jinho-study.tistory.com
백준 알고리즘 13565번 침투(python)
기본적인 DFS & BFS 문제이다. 첫번째 줄만 탐색을 시킨 후에 마지막 줄이 탐색이 된 적 있으면 "YES" 아니면 "NO"를 출력해주면 된다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): graph..
jinho-study.tistory.com
백준 알고리즘 12761번 돌다리(python)
기본적인 BFS 문제이다. from collections import deque def bfs(node): q = deque() q.append(node) graph[node] = 0 while q: node = q.popleft() for n in [node-1, node+1, node+A, node-A, node+B, node-B, n..
jinho-study.tistory.com
백준 알고리즘 3187번 양치기 꿍(python)
기본적인 DFS & BFS 문제이다. 3184번 양과 거의 동일한 문제이다. 그냥 BFS으로만 풀었다. BFS 풀이 from collections import deque def bfs(y, x): queue = deque() queue.append((y, x)) s = w = 0 while queue..
jinho-study.tistory.com
백준 알고리즘 18405번 경쟁적 전염(python)
생각보다 어려운 BFS 문제이다. 바이러스가 퍼지는 순서(작은 숫자부터)에 맞게 def bfs(x, y): check[x][y] = 1 for dx, dy in d: X, Y = x+dx, y+dy if (0 <= X < N) and (0 <= Y < N) and graph[X][Y] == 0: ch..
jinho-study.tistory.com
백준 알고리즘 14716번 현수막(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): graph[y][x] = 0 for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < M) and (0 <= X < N) and graph[Y][X] ==..
jinho-study.tistory.com
백준 알고리즘 16956번 늑대와 양(python)
기본적인 BFS 문제이다. 양과 늑대가 인접해있으면 막을 수가 없으므로 0을 출력해주고, 인접한 경우가 없다면 늑대를 가둬버리고 결과를 출력해주면 된다. from collections import deque def bfs(y, x): for
jinho-study.tistory.com
백준 알고리즘 1303번 전쟁 - 전투(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x, cnt): c = graph[y][x] graph[y][x] = 1 for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < M) and (0 <= X < N..
jinho-study.tistory.com
백준 알고리즘 17806번 아기 상어 2(python)
브루트포스 알고리즘 & BFS 문제이다. from collections import deque from copy import deepcopy def bfs(y, x): q = deque() q.append((y, x)) a[y][x] = 0 while q: y, x = q.popleft() for dy, dx in d: Y, X..
jinho-study.tistory.com
백준 알고리즘 6186번 Best Grass(python)
기본적인 BFS 문제이다. from collections import deque def bfs(y, x): q = deque() q.append((y, x)) graph[y][x] = '1' while q: y, x = q.popleft() for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < R) and..
jinho-study.tistory.com
백준 알고리즘 11123번 양 한마리... 양 두마리...(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): graph[y][x] = '.' for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < H) and (0 <= X < W) and graph[Y][X] =..
jinho-study.tistory.com
백준 알고리즘 17198번 Bucket Brigade(python)
기본적인 BFS 문제이다. from collections import deque def bfs(y, x): q = deque() q.append((y, x)) graph[y][x] = 0 while q: y, x = q.popleft() for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < 10) and (..
jinho-study.tistory.com
백준 알고리즘 4677번 Oil Deposits(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): graph[y][x] = '*' for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < m) and (0 <= X < n) and graph[Y][X] =..
jinho-study.tistory.com
백준 알고리즘 18232번 텔레포트 정거장(python)
기본적인 BFS 문제이다. from collections import deque import sys def bfs(node): q = deque() q.append(node) check[node] = 0 while q: node = q.popleft() d = [node-1, node+1] if graph[node]: d += graph[..
jinho-study.tistory.com
백준 알고리즘 18243번 Small World Network(python)
기본적인 BFS 문제이다. from collections import deque def bfs(node): q = deque() q.append(node) check[node] = 0 while q: node = q.popleft() for n in graph[node]: if check[n] == -1: q.append(n) check[..
jinho-study.tistory.com
백준 알고리즘 18404번 현명한 나이트(python)
기본적인 BFS 문제이다. from collections import deque def bfs(y, x): q = deque() q.append((y, x)) graph[y][x] = 0 while q: y, x = q.popleft() for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < N) and (0..
jinho-study.tistory.com
백준 알고리즘 8061번 Bitmap(python)
기본적인 BFS 문제이다. 처음에 '1'의 위치들을 queue에 모두 추가해놓고 bfs를 돌리면 쉽게 풀 수 있다. 간단하지만 여태까지 풀어왔던 문제랑 조금 느낌이 달라서 푸는데 시간이 조금 걸렸다. from c
jinho-study.tistory.com
백준 알고리즘 15240번 Paint bucket(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x, K, n): graph[y][x] = K for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < R) and (0 <= X < C) and graph[Y][..
jinho-study.tistory.com
백준 알고리즘 14248번 점프 점프(python)
기본적인 BFS 문제이다. from collections import deque def bfs(node): q = deque() q.append(node) check[node] = 1 while q: node = q.popleft() for d in [-graph[node], graph[node]]: t = node+d if (0 <= t..
jinho-study.tistory.com
백준 알고리즘 15092번 Sheba’s Amoebas(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): graph[y][x] = '.' for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < m) and (0 <= X < n) and graph[Y][X] =..
jinho-study.tistory.com
백준 알고리즘 5938번 Daisy Chains in the Field(python)
기본적인 DFS & BFS 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(node): check[node] = 1 for n in graph[node]: if check[n] == 0: dfs(n) N, M = map(int, input().split()) graph =..
jinho-study.tistory.com
백준 알고리즘 5931번 Cow Beauty Pageant(python)
생각보다 쉽지 않은 BFS 문제이다. 우선 'X'를 '1'과 '2'로 각각 채워주고, 1에서 2로 가는 최소 거리를 찾아주면 된다. 1이 1안에 갇혀서 2로 갈 수도 없는 경우가 있으므로 이 경우는 따로 잘 처리해
jinho-study.tistory.com
백준 알고리즘 10917번 Your life(python)
기본적인 BFS 문제이다. import sys from collections import deque def bfs(node): q = deque() q.append(node) check[node] = 0 while q: node = q.popleft() for n in graph[node]: if check[n] == -1: q.appen..
jinho-study.tistory.com
백준 알고리즘 6031번 Feeding Time(python)
기본적인 BFS 문제이다. '.'을 1, 2, 3...으로 채울 때마다 각각 몇 개를 채웠는지 확인하고, 그중 최댓값을 출력해주면 된다. from collections import deque def bfs(y, x, t): q = deque() q.append((y, x)) gr..
jinho-study.tistory.com
백준 알고리즘 11370번 Spawn of Ungoliant(python)
기본적인 BFS 문제이다. from collections import deque def bfs(y, x): q = deque() q.append((y, x)) while q: y, x = q.popleft() for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < H) and (0 <= X < W) and g..
jinho-study.tistory.com
백준 알고리즘 16390번 Sheba’s Amoebas(python)
기본적인 DFS & BFS 문제이다. 15092번 Sheba’s Amoebas와 같은 문제이다. DFS 풀이 import sys sys.setrecursionlimit(3000000) def dfs(y, x): graph[y][x] = '.' for dy, dx in d: Y, X = y+dy, x+dx if (0 <=..
jinho-study.tistory.com
백준 알고리즘 1325번 효율적인 해킹(python)
DFS & BFS 문제이다. 그런데 DFS로 풀면 시간초과가 계속 나와서 그냥 BFS로만 풀었다. 입력을 받을 때는 sys.stdin.readline을 사용하고, Python3가 아닌 PyPy3로 제출해야 통과된다. BFS 풀이 from collections..
jinho-study.tistory.com
백준 알고리즘 14496번 그대, 그머가 되어(python)
단순한 BFS 문제이다. 근데 a == b일 때를 생각 못하고 처리를 안 해서 엄청나게 많이 틀렸다. 주의하도록 하자 from collections import deque def bfs(a, b): q = deque() q.append(a) check[a] = 0 while q: no..
jinho-study.tistory.com
백준 알고리즘 14145번 Žetva(python)
기본적인 DFS & BFS 문제이다. 처음에 그래프를 생성할 때 graph = [map(int, list(input())) for _ in range(R)] 와 같은 방식으로 생성해서 계속 메모리 초과가 나왔다. graph = [list(input()) for _ in range(..
jinho-study.tistory.com
백준 알고리즘 10204번 Neighborhoods in Graphs(python)
기본적인 BFS 문제이다. 특정 노드에서부터 거리가 2 이하인 노드가 몇 개 인지 출력하면 되는 문제이다. from collections import deque def bfs(node): q = deque() q.append(node) check[node] = 0 while q: no..
jinho-study.tistory.com
백준 알고리즘 13746번 Islands(python)
기본적인 BFS 문제이다. L(땅)이 탐지될 때마다 BFS를 돌리고 카운트를 세는데 이때 C(구름)는 L이라고 생각하고 처리하면 된다. from collections import deque def bfs(y, x): q = deque() q.append((y, x)) gra..
jinho-study.tistory.com
백준 알고리즘 18422번 Emacs(python)
기본적인 BFS 문제이다. from collections import deque def bfs(y, x): q = deque() q.append((y, x)) graph[y][x] = '.' while q: y, x = q.popleft() for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < r) and..
jinho-study.tistory.com
백준 알고리즘 6189번 Munching(python)
기본적인 BFS 문제이다. B에서 C로 가는 최단거리의 길이를 출력해주면 된다. from collections import deque def bfs(y, x): q = deque() q.append((y, x)) graph[y][x] = 0 while q: y, x = q.popleft() for dy,..
jinho-study.tistory.com
백준 알고리즘 6080번 Bad Grass(python)
기본적인 DFS & BFS 문제인데 DFS로는 메모리 초과 때문에 통과가 안 되는 것 같다. BFS로 제출하면 통과된다. BFS 풀이 from collections import deque def bfs(y, x): q = deque() q.append((y, x)) graph[y][x]..
jinho-study.tistory.com
백준 알고리즘 6004번 The Chivalrous Cow(python)
기본적인 BFS 문제이다. from collections import deque def bfs(y, x): q = deque() q.append((y, x)) graph[y][x] = 0 while q: y, x = q.popleft() for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < N) and (0..
jinho-study.tistory.com
백준 알고리즘 6229번 Bronze Lilypad Pond(python)
기본적인 BFS 문제이다. from collections import deque def bfs(y, x): q = deque() q.append((y, x)) graph[y][x] = 0 while q: y, x = q.popleft() for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < M) and (0..
jinho-study.tistory.com
백준 알고리즘 9019번 DSLR(python)
생각보다 쉬운 BFS 문제이다. 변환된 숫자와 여태까지 사용한 명령어를 큐에 같이 append, pop 해주면 된다. 변환된 숫자와 B가 같다면 여태까지 사용한 명령어(res)를 리턴하면 끝이다. from collections i
jinho-study.tistory.com
백준 알고리즘 6798번 Knight Hop(python)
기본적인 BFS 문제이다. from collections import deque def bfs(y, x): q = deque() q.append((y, x)) graph[y][x] = 0 while q: y, x = q.popleft() for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y < 8) and (0..
jinho-study.tistory.com
백준 알고리즘 11448번 Ga(python)
기본적인 BFS 문제이다. from collections import deque def bfs(y, x): q = deque() q.append((y, x)) graph[y][x] = 'w' cnt = 0 while q: y, x = q.popleft() for dy, dx in d: Y, X = y+dy, x+dx if (0 <= Y <..
jinho-study.tistory.com
백준 알고리즘 5558번 チーズ(python)
S에서 시작해서 1부터 N까지 순서대로 들렀을 때의 최단거리를 구해야 되는 BFS 문제이다. 1에 들러야 된다고 해서 2를 지나가면 안 된다는 것은 아니다. 목적지(1, 2, ... N)에 도착할 때마다 시작점
jinho-study.tistory.com
백준 알고리즘 12852번 1로 만들기 2(python)
다이나믹 프로그래밍 or 그래프 탐색 문제이다. 다이나믹 프로그래밍 풀이 N = int(input()) dp = [[0, []] for _ in range(N+1)] dp[1][0] = 0 dp[1][1] = [1] for i in range(2, N+1): dp[i][0] = dp[i-1][0] +..
jinho-study.tistory.com
백준 알고리즘 13549번 숨바꼭질 3(python)
너비 우선 탐색 or 다익스트라 문제인데 그냥 너비 우선 탐색으로 풀었다. 이전 숨바꼭질 문제와는 다르게 순간이동할 때 걸리는 시간이 0이다. 이 점 때문에 node-1, node+1보다 node*2를 먼저 탐색을
jinho-study.tistory.com
https://jinho-study.tistory.com/1075
백준 알고리즘 1326번 폴짝폴짝(python)
앞, 뒤 방향과 노드별 이동거리 모두 고려해줘야 되는 bfs 문제이다. 아래와 같이 앞, 뒤 방향의 경우로 둘로 나눠서 반복문을 짜면 96ms로 통과된다. from collections import deque def bfs(a, b, bridge, N): q..
jinho-study.tistory.com
https://jinho-study.tistory.com/1076
백준 알고리즘 1326번 폴짝폴짝(python)
기본적인 BFS 문제이다. B가 200점 이상이 되는 최단경로는 없을 것 같아서 check 리스트 크기를 200으로 정했다. from collections import deque def bfs(S, T): q = deque() q.append((S, T, 0)) check = [-1]*..
jinho-study.tistory.com
https://jinho-study.tistory.com/1084
프로그래머스 Level 3 가장 먼 노드
1번 노드에서 제일 먼 노드가 몇 개 인지 찾는 문제이다. BFS로 아주 쉽게 풀 수 있다. from collections import deque def solution(N, edge): graph = [[] for _ in range(N+1)] for a, b in edge: graph[a].app..
jinho-study.tistory.com
https://jinho-study.tistory.com/1087
프로그래머스 Level 3 네트워크
간단한 그래프 탐색 문제이다. 반복문을 돌면서 체크가 안된 노드가 있다면 ans += 1을 하고 그 노드부터 시작하여 dfs 또는 bfs를 돌려서 갈 수 있는 길을 다 체크해주면 된다. check[i] = 0 -> i 노드 들
jinho-study.tistory.com
https://jinho-study.tistory.com/1099
백준 알고리즘 16173번 점프왕 쩰리 (Small)(python)
기본적인 BFS, DFS 문제이다. (N, N) 좌표에 도착할 수 있는지를 확인해주면 된다. BFS 풀이 from collections import deque def bfs(y, x): q = deque() q.append((y, x, li[y][x])) while q: y, x, d = q.poplef..
jinho-study.tistory.com
https://jinho-study.tistory.com/1100
백준 알고리즘 17204번 죽음의 게임(python)
기본적인 그래프 탐색 문제이다. 최단거리를 찾는 문제이므로 BFS로 풀었다. from collections import deque def bfs(): q = deque() q.append((0)) while q: node = q.popleft() n = li[node] if check[n] == 0 a..
jinho-study.tistory.com
https://jinho-study.tistory.com/1107
백준 알고리즘 9311번 Robot in a Maze(python)
간단한 BFS 문제이다. S에서 G로 가는 최단경로의 길이를 출력해주면 된다. 경로가 없다면 No Exit 출력 from collections import deque def bfs(i, j): d = [(-1, 0), (1, 0), (0, -1), (0, 1)] q = deque() q.ap..
jinho-study.tistory.com
'Agorithm > 자료구조, 알고리즘 정리' 카테고리의 다른 글
| 퇴각검색(Backtracking) (백준 문제 포함) (0) | 2021.03.20 |
|---|---|
| 동적 계획법(Dynamic programming) (백준 문제 포함) (0) | 2021.03.17 |
| 깊이 우선 탐색(depth-first search, DFS) (백준 문제 포함) (0) | 2021.03.10 |
| 큐(Queue), 덱(Deque) (백준 문제 포함) (0) | 2021.03.05 |
| 스택(Stack) (백준 문제 포함) (0) | 2021.03.05 |