# BFS

264개의 포스트
post-thumbnail

BFS(Breadth First Search, 너비 우선 탐색)

BFS(Breadth First Search, 너비 우선 탐색)란 루트 노드(혹은 임의 노드)에서 시작해서 인접한 노드들 부터 탐색하는 방법이다. 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 탐색 방법이다.

약 11시간 전
·
0개의 댓글
post-thumbnail

[SWEA]#1210 [S/W 문제해결 기본] 2일차 - Ladder1

문제점심 시간에 산책을 다니는 사원들은 최근 날씨가 더워져, 사다리 게임을 통하여 누가 아이스크림을 구입할지 결정하기로 한다.김 대리는 사다리타기에 참여하지 않는 대신 사다리를 그리기로 하였다.사다리를 다 그리고 보니 김 대리는 어느 사다리를 고르면 X표시에 도착하게

5일 전
·
0개의 댓글
post-thumbnail

[백준]#5567 결혼식

문제상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를

6일 전
·
0개의 댓글

[백준] 16948번. 데스 나이트

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.크기가

6일 전
·
0개의 댓글

[백준] 7562번. 나이트의 이동

[백준] 7562번. 나이트의 이동 1. 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 2. 입력 입력의 첫

6일 전
·
0개의 댓글
post-thumbnail

[문제풀기] 백준 #1260 (DFS와 BFS)

백준 1260번(DFS와 BFS)의 풀이

6일 전
·
1개의 댓글

[백준] 1389번. 케빈 베이컨의 6단계 법칙

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호

6일 전
·
0개의 댓글

[백준] 5567번. 결혼식

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕

7일 전
·
0개의 댓글

[백준] 2660번. 회장뽑기

월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.예를 들어 어

7일 전
·
0개의 댓글

[백준] 13549번. 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로

7일 전
·
0개의 댓글

[백준] 9019번. DSLR

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1,

7일 전
·
0개의 댓글

[백준] 1697번. 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로

2020년 10월 19일
·
0개의 댓글
post-thumbnail

[백준]#5427 불

문제상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초

2020년 10월 16일
·
0개의 댓글
post-thumbnail

[백준 2178] 미로탐색 | BFS

N×M크기의 배열로 표현되는 미로가 있다.1 0 1 1 1 11 0 1 0 1 01 0 1 0 1 11 1 1 0 1 1미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)

2020년 10월 14일
·
0개의 댓글
post-thumbnail

[백준 2667] 단지번호 붙이기 | BFS

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집

2020년 10월 14일
·
0개의 댓글
post-thumbnail

[백준 7576] 토마토 | BFS

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지

2020년 10월 14일
·
0개의 댓글
post-thumbnail

프로그래머스 - 네트워크[lv3] (BFS)

프로그래머스 문제풀이 - BFS

2020년 10월 12일
·
0개의 댓글
post-thumbnail

[알고리즘] 백트래킹(되추적)

어떤 노드의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 그 노드의 후손 노드(서브 트리)들에 대한 검색을 중지하고, 그 노드의 부모노드(parent)로 돌아간다 ("backtrack").DFS는 가능한 모든 경로(후보)를 탐색합니다. 즉, 불필요한 노드까지 모두

2020년 10월 12일
·
0개의 댓글
post-thumbnail

프로그래머스 - 타겟 넘버[lv 2](DFS)

프로그래머스 문제풀이 - DFS

2020년 10월 12일
·
0개의 댓글
post-thumbnail

[알고리즘] BFS(너비우선탐색)과 DFS(깊이우선탐색)

현재 정점에서 연결된 가까운 점들부터 탐색하는 방법큐(Queue) 자료구조 이용pop(0) 은 시간복잡도가 O(N) 이라 매우 비효율적인 코드가 만들어 진다. 따라서 collections 라이브러리의 deque를 사용한다.현재 정점에서 갈 수 있는 점들까지 들어가면서

2020년 10월 11일
·
0개의 댓글