BFS(너비 우선 탐색) 알고리즘에 대해 알아보기 전에 필수적으로 알아봐야 할 자료구조는 바로 그래프(Graph)다. 그래프는 실질적으로 프로그래밍 언어 라이브러리 상에서 제공하기 보다는 추상적인 자료구조로써 개념을 차용하여 알고리즘에 응용하여 푸는 경우가 많으므로, 자료구조 카테고리가 아닌 알고리즘 카테고리에서 함께 다루고자 한다. 그래프 그래프의 정의 및 개념 그래프(G)는 정점 집합(V)과 간선 집합(E)으로 구성된 자료구조로, 대상과 대상 간의 관계를 나타내는 자료구조다. 그래프는 다들 너무나도 익숙하게 들어봤을 '쾨니히스베르크(Königsberg) 다리'를 보고 수학자 오일러가 '한붓그리기' 문제를 해결하기 위해 고안한 것으로 알려져 있기도 하다. 이 고안법에서 중요한 것은, 각 육지를 잇는 다..

1. 문제: https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, www.acmicpc.net 2. 풀이 문제의 핵심 조건은 아래와 같다. 1) 상하좌우 뿐만 아니라 대각선으로도 움직일 수 있다. 2) 방문하는 장소들 중 고도의 최고점과 최저점의 차이를 '피로도'라고 하며 이를 최소화 해야한다. 대각선을 추가하는 것이야 방향을 설정해주는 dy, dx 배열만 추가로 설정해주면 되는데 피로도를 최소화하기 위해서는 어떤 방법을 써야할 것 인가? 지도에서 주어진 모..

1. 문제: https://www.acmicpc.net/problem/9328 9328번: 열쇠 문제 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열 www.acmicpc.net 2. 풀이 지도 상에서 돌아다니면서 문을 만났을 때 열쇠가 있다면 열고 들어가고 없으면 열지 못하는 본 문제와 비슷한 유형의 문제를 백준에서 풀었던 기억이 있다. 그 문제가 뭐였는지 기억한다면 첨부하도록 하겠다.... 아무튼 문제의 상근이가 문서를 훔치기 위해서 빌딩 내부를 돌아다녀야 하는데 문제의 중요한 몇 가지만 인지하고 있다면 크게 어려울 것은 없다. 1) 상근이의 출발점이 정해지지 않았으..