0. 그래프 탐색의 기본인 DFS와 BFS그래프 탐색이란 무엇인가?그래프 탐색이란, 정점과 간선으로 이루어진 그래프에서 특정 정점을 선택하고, 해당 정점에서 인접한 정점을 방문하는 것을 말한다. 이러한 정점 방문 방법에는 크게 2가지가 있는데, 이것이 앞으로 살펴볼 DFS와 BFS이다.우리는 위의 그래프를 예시로 사용하며 하나씩 이해해 보겠다.1. DFSDFS는 Depth First Search의 약자로 깊이 우선 탐색을 뜻한다. 말 그대로 방문하기로 정한 인접 정점의 최대 깊이까지 탐색을 마친 후, 다음 인접 정점을 확인하는 것이다. 알고리즘 논리는 다음과 같다.(1) 현재 정점과 인접한 정점을 방문한다.(2) 방문한 정점에서 아직 방문하지 않은 정점이 있다면 방문하지 않은 정점을 모두 방문할 때까지 ..

1. 문제 설명문제 링크 2. 접근 방식KEY WORD: BFS생각 해야할 점: 하나의 정점이 자신의 위치를 안다는 것은 단방향 그래프에서 해당 정짐이 다른 모든 정점들과 서열를 가진다는 것이다. 이 때, 해당 서열은 간접적으로 파악이 되도 된다.간접적으로 파악된다는 것은 무슨 뜻인가?해당 그림은, 문제에서 예시로 주어진, 정점들간의 관계이다. 문제에서는 2번이 1,4,3번에게 패하고, 5번에게 이겼음으로 4등이라고 했다. 5번은 그 2번에게 졌음으로, 1,3,4번에게도 간접적으로 진 것이다. 따라서 2, 5번은 모든 정점에 대해서 서열을 가진다.(1) 단 방향 그래프를 두 개 만들기첫 번째 방법은 단 방향 그래프 2개 만들기 이다.우리의 핵심은, 현재 조회 중인 정점이 간접적으로라도, 모든 정점과 서열..

1. 문제 설명2. 접근 방식KEY WORD: BFS, IDEA해당 문제는 문제를 풀기 위한 IDEA만 생각해낸다면 간단한 BFS 문제이다. 문제에 대한 접근 방식은 다음과 같다.(1) 입력받은 좌표의 변두리 부분도 페인트를 칠할 수 있다. 가령파란색으로 칠한 부분을 봐라. 만약 입력 좌표 그대로 2차원 배열을 만든다면, 해당 변두리 부분은 배열을 벗어나게 되어, 페인트를 칠할 때 골치가 아파진다. (자칫 잘못하면 OutOfArrayIndex 에러가 나기 때문이다!!)따라서 우리는 해당 좌표도 배열 내에서 받을 수 있도록 2차원 배열을 테두리까지 넉넉하게 만들고, 여기에 입력받은 좌표값들을 집어넣는다.int [][] map = new int [row+2][col+2]그러면 이렇게 받을 수 있다. 파란색으..

1. 문제 설명문제 설명2. 접근 방식KEY WORD: BFS2차원 배열에 값을 담는다.번호 별로 의미가 있다. (0 = 벽, 1 = 미방문한 아파트 단지, 2 = 방문한 단지)(1) 2차원 배열을 순회하다가 값 == 1인 것을 만나면, 해당 값을 시작으로 BFS를 돌린다. 현재 값의 사방을 탐색한다. 사방의 값 중 1인 값이 있으면 큐에 넣고, 해당 위치의 값을 2로 바꾼다. 큐가 빌 때 까지 (더 이상 사방 탐색을 해도 값 = 1이 안 나올 때 까지) 반복한다.(2) 1번은 첫 조회에서 만난 아파트의 아파트 단지 전체를 한번에 보는 것이다. 따라서 1번의 반복 횟수가 곧 아파트의 개수이다.(3) 아파트 단지를 단지내 아파트의 개수에 따라 오름차순으로 정렬한다. 3. 코드 분석import java.i..