본문 바로가기

Algorithm/BFS

 (3)
카카오프렌즈 컬러링북 문제설명 : 출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.) 그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자. 위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다. 입력 형식 입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다. 1
게임 맵 최단거리 난이도 level2 문제 programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 제한사항 maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다. n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다. maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자..
Breadth-first search 기본개념 알고리즘 공부를 시작하면서 생소한 단어들이 너무나 많고 개념도 잡히지 않은 상태 이기 때문에 간단히 정리 하고자 한다. 우선 넓이우선탐색(BFS)은 트리를 예로 들어서 많이 설명해 주는 것 같았고 반대되는 개념으로는 깊이우선탐색(Depth-First Search) 있다. 단어 뜻 그대로 가장 깊은곳을 먼저 탐색하느냐 or 내 주위에 가까운 곳부터 전부 탐색하고 다음 깊이의 단계를 탐색 할 것 인지를 구분하고 있다. 넓이 우선 탐색 은 물결처럼 퍼지듯 가까운 경로의 후보부터 탐색을 한다고 하는데 아래의 그림을 보면 바로 이해는 된다. 위의 그림에서 처럼 BFS 는 depth 가 같은 노드를 먼더 탐색하고 다음 depth로 이동 한다. 그런데 두 탐색알고리즘의 장점은 무엇일까?? 장점 1. BFS를 사용하면..

티스토리툴바