#BFS 9

• PS 2024-05-23

  [간만에 스터디] LeetCode Number of Provinces

  Number of Provinces 코드 접근 및 풀이방법 1. 그래프탐색(BFS or DFS)은 그래프에 존재하는 모든 간선을 통해 결국 모든 노드를 방문한다. 1. 단 이 문제의 경우 그래프가 양방향 간선이 존재하기 때문에 반드시

• PS 2022-01-14

  백준 13913 숨바꼭질 4

  문제 수빈이는 점 N 에, 동생은 점 K 에 있다. 수빈이는 1초에 걷기 ( X-1 또는 X+1 ) 또는 순간이동 ( 2 X )을 할 수 있다. 동생을 찾는 가장 빠른 시간과, 그때 거쳐 간 위치들 을 출력하면 된다. - 입력 : N

• PS 2021-12-29

  백준 2251 물통

  문제 용량이 각각 A , B , C 인 물통 셋이 있다. 처음엔 C 만 가득 차 있고 A , B 는 비어 있다. 한 물통에서 다른 물통으로, 받는 쪽이 가득 차거나 주는 쪽이 빌 때까지 물을 부을 수 있다. 첫 번째 물통( A )이

• PS 2021-11-25

  백준 1941 소문난 칠공주

  문제 5 × 5 격자에 학생 25명이 앉아 있다. 각 자리는 '이다솜파'( S ) 또는 '임도연파'( Y )다. 다음 조건을 모두 만족하는 7명을 뽑는 경우의 수 를 구하면 된다. 1. 7명이어야 한다. 2. 7명이 가로·세로로 모두

• PS 2021-06-30

  백준 1194 달이 차오른다, 가자

  문제 미로를 탈출하는 최소 이동 횟수를 구한다. 빈 곳 . 은 지날 수 있고 벽 은 못 지난다. 열쇠 a f 는 밟으면 줍고, 문 A F 는 대응하는 열쇠가 있어야 지날 수 있다. 시작 0 에서 출구 1 로 가면 된다. - 입력 :

• PS 2020-12-30

  백준 2583 영역 구하기

  문제 M × N 모눈종이에 K 개의 직사각형을 칠한다. 칠하지 않은 나머지 부분이 몇 개의 분리된 영역 으로 나뉘는지, 그리고 각 영역의 넓이가 얼마인지 구하면 된다. - 입력 : 1번째 줄에 M N K , 이어서 K 줄에 직사각형의

• PS 2020-11-07

  백준 3055 탈출

  문제 숲이 격자로 주어진다. 고슴도치 S 는 비버굴 D 로 가야 하는데, 물 이 매 분 인접한 빈 칸으로 퍼진다. 고슴도치도 매 분 인접한 빈 칸으로 이동하며, 물이 찰 칸으로는 갈 수 없다. 돌 X 는 물도 고슴도치도 못 지난다.

• PS 2020-08-27

  백준 4991 로봇 청소기

  문제 방이 격자로 주어진다. 로봇 청소기 o 가 한 칸에 있고, 더러운 칸 이 여러 개, 빈 칸 . , 가구(벽) x 가 있다. 로봇은 상하좌우로 한 칸씩(1분) 움직이며 가구는 지날 수 없다. 모든 더러운 칸을 청소하는 데 드는 최

• PS 2018-05-13

  너비 우선 탐색 (BFS) 정리

  BFS (너비 우선 탐색) 시작 정점에서 가까운 정점부터 차례대로, 레벨 단위로 퍼져 나가며 탐색하는 방법. 큐(Queue)를 사용한다. DFS가 한 갈래를 끝까지 파고드는 것과 반대로, BFS는 시작점에서 거리 1인 정점들을 모두