https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 이 문제는 가볍게 BFS 문제로 풀 수가 있다. BFS를 돌릴 떄마다 각각의 max값을 구한 후, 그 값과 다음으로 나올 값을 비교하면서 가장 큰 값을 찾아나가면 된다. package BFS; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedL..
https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 빙산 문제와 마찬가지로, BFS 알고리즘을 활용해 치즈에 닿은 면이 있으면 그 치즈를 없애준 후, 남아있는 치즈를 계산한다. 그 과정을 반복하여 코드를 작성하면 아래와 같은 코드로 만들 수 있다. package BFS; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.C..
이 문제를 보고 입력창을 보자마자 이건 BFS로 풀어야 되겠다는 생각이 바로 들었다. Queue 배열에 들어갈 때 마다 영역의 넓이를 하나씩 늘리는 방법으로 풀면 생각보다 쉽게 풀 수 있다. 처음부터 끝까지 다 돌면서 아직 돌지 않은 영역을 BFS의 시작 지점으로 만들어서 전부 탐색할 수 있게 만들었다. from collections import deque def bfs(graph, start): dx = [-1,1,0,0] dy = [0,0,-1,1] queue = deque() queue.append(start) area = 0 isnothing = True while queue: x,y = queue.popleft() for i in range(len(dx)): nx = x+dx[i] ny = y+..
BFS 알고리즘이란 너비 우선 탐색이라고 부르며 그래프에서 가장 가까운 노드부터 탐색해 점점 거리를 벌려가는 알고리즘이다. 이 알고리즘을 사용하기위해 Queue를 사용한다. Queue는 FIFO구조이기 때문에 이 구조를 이용하여 알고리즘을 만들면 BFS의 시작점이 중간에 있으면 노드의 방문을 그려보면 동심원으로 이루어지게 된다. DFS 알고리즘은 BFS 알고리즘을 그대로 Queue가 아닌 스택으로 사용하여 구현한 알고리즘이다. 아쉬운점은 처음 시작점에서 DFS 순서대로 이동하면 시작점에서 이동한 거리가 비례해서 증가하지 않는다는 것이다. 이렇게 BFS와 DFS가 어떤 방식으로 구현되는지 알아보았고, 이 알고리즘을 코드로 써본다면 아래와 같은 코드가 될 것이다. from collections import ..
