개발자 모드

이번 글에서는 그래프를 탐색하는 방법 중 하나인 BFS에 대해서 다뤄보겠습니다. BFS란? BFS는 Breath-First Search의 줄임말로, 하나의 정점에서 시작하여 해당 정점과 이웃한 모든 정점을 방문한 뒤, 방문한 정점들의 이웃 정점을 방문하는 방식을 의미합니다. BFS의 탐색 순서를 아래의 그림을 통해 쉽게 확인하실 수 있습니다. BFS의 구현 BFS를 자바로 구현해보겠습니다. import java.util.*; public class Edge{ // 각 노드를 정의 int adjvertex; public Edge(int v){ adjvertex = v; } } public class BFS{ int N; List[] graph; private boolean[] visited; public ..

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 1. 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을..

오늘은 기본적인 알고리즘인 DFS와 BFS에 대해서 알아보겠습니다. BFS란? BFS란 Breadth-First Search의 약자로 번역하면 너비 우선 탐색입니다. 이는 트리 구조에서 많이 사용되곤 합니다. 어떤 대상 노드로부터 가장 가깝게 연결된 노드들부터 탐색하며 순차적으로 트리의 전체를 순회하는 구조를 일컫습니다. (트리의 용어가 어색한 분들은, 아래의 그림을 보고 우선은 단순하게 이런 식으로 생긴 놈이구나 라고 생각하시면 좋을 것 같습니다.) 아래의 자료를 보면 금방 이해하실 수 있습니다. 루트 노드인 1로부터 가장 가깝게 연결된 3개를 순서대로 순회합니다. 그 후, 2와 연결된 노드를 방문하고, 최종적으로는 트리의 모든 노드를 방문하는 방법입니다. 그럼 BFS의 소스 코드를 살펴보겠습니다. 제..