으 [음악] 네 안녕하세요 비전공자 댁 역가 기 안장 보입니다 네 오늘은 코딩 테스트 첫 번째 시간인데요 BFS 부터

시작하도록 할게요 4 우선은 BFS 는 그래프 탐색 에 한 방법이에요 그래프 탐 서기 탐색이 뭐냐 g 보다

음색을 어떤 것들이 연속해서 이어질 때 모두 확인하는 방법을 그래프 탐색 이라고요 예를 한번 들어 볼게요 자

여기서 이런 식으로 그래프가 나와 있을 때 이렇게 어떤 것들이 연속해서 이어지고 있어요 그러면은 이것들을 모두 확인해

보는 방법을 그래프 탐색 이라구요 예를 들면 은 자 여기서 시작을 해서 여기를 보고 여기를 보고 이런 식으로 가는것을 그래프 탐색 이라고 합니다

근데 여기서 이제 어떤 것들 이 어떤거를 버텍스 라고 하고요 이 이어져 있는 것을 엣지 라고 해요 네

그래서 이렇게 어떤 것들이 연속해서 이어져 있을 때 그래서 모두 확인해라는 방법 예를 들면 은 뭐 여기에

별표 별이 있는데 왕이 살고 있는데 이 왕을 찾는다든지 아니면 총 이게 몇 개 있는지를 조사한다던지 이렇게

모두 확인하는 방법을 그래프 탐색이라고 합니다 그럼 그래프 탐색에는 크게 DFS 와 BFS 가 있어요 자 BFS 는 이제 너비를 먼저 우선 탐색을 하는

거고요 DFS 는 깊이를 우선 탐색을 하는 거예요 내려가서 만들어 볼게요 자 이런 식으로 그래프가 있다고 치면

은 이런 식으로 따져 볼게요 자 BFS 는 자기 자식을 우선 먼저 탐색을 해요 그러니까 여기서 시작을 했다면 은

여기 자식들 먼저 그 다음 보게 될 거고요 자식들을 먼저 보게 된 다음 자식을 먼저 우선으로 보게 된 다음 그

다음에 자식의 또 그럼 그 다음 자식의 또 자식을 먼저 보게 된 거죠. 그 다음에 또 자식을 보게 되고

근데 DFS 했을 때 뭐가 되면 난 요 순서가 살짝 달라요. DFS 는 그 자식의 자식을 먼저 구성을 보게 돼요.

예를 들면 볼게요. 이런 식으로 그래프가 또 있고 또 이런 식으로 그래프가 있을 때 자 여기서 먼저 시작을 했다고 치면

은 여기서 시작을 했다고 치면 은 자식을 먼저 보고요. 그 다음에 자식의 자식을 그다음 보게 돼 있어요. 자식이 없으면

그 위로 올라와서 그 다음 자식, 그 다음에 또 위로 올라서 그 다음 자식, 자식, 그 다음에 올라와서 자식 이런 식으로요. 이어 하시나요? 자 그러면

이런 예제가 있을 때 PFS 는 이제 일본에서 시작을 했다고 쳐 볼게요. 그럼 어떤 식으로 될까요? 이번 을 보고

3번 5번을 보겠죠 자 그러면 일본 이번 5번을 있겠죠 자 그럼 다음에 입원을 확인해 보면서

2번은 먹어 이어졌죠 1 5 3 2 있는데 일본과 오거나 없다 이미 확인이 됐잖아요 그래서 3번을 3번만

새로 추가되고 요 그 다음에 입원을 확인할 차례 에서는 1 2 4 가 추가되어 있는데 2 3 2 일은 이미 확인이 됐으니까 4번이

추가되어 있죠 그 3번에서 느 3번에서 사가 이미 확인돼 있으니까 새로운 추가되지 않게 있구요 4번 에서는 여기서 유기 추가

되겠죠 그래서 초 순서가 1 2 5 3 사유 이렇게 되겠죠 자금 기회에 패션 어떻게 되는지 알아볼게요

DFS 는 이제 깊이 우선 탐색 이라고 자식을 자신을 먼저 보는 거죠 자 먼저 볼게요 일에는 이와 5일

자식이 있죠 형 길은 일을 먼저 갈 거예요 그래서 이 이애 5를 가는 게 아니고 이에 자식을 못 하겠죠 그 다음에 사람이죠

그 다음에 3회에서는 살을 갈 테고 4에서는 오랑 유기 있죠 근데 오는 이미 일이 지금 침을 해 놓은

상태거든요 그래서 6을 갈 테고요 이젠 위기에서 이제 더 이상 갈 데가 없으니까 올라 올라 올라 올라 와서

1에서 복원해 버렸죠 그래서 이런 식으로 가는 게 깊이 우선 탐색입니다 그래서 오늘은 bfs 를 어떻게

코드로 구현하고 문제를 푸는지를 먼저 확인을 해볼 거예요 자 그러면 dfs 를 어떻게 g 코드로 구현을 할까

우선은 먼저는 각각의 버텍스에 이제 연결된 2 코텍스들을 찾아요 궁리 버텍스들을 q 에 저장을 해야

되는데요 Q 를 저장을 해서 가장 원자 값을 뽑아서 이걸 반복하는 행동을 계속 반복하는 거죠 자 그럼

여기서 키와 어 휴 를 잡아 설명드릴께요 큐는 자료구조 중에 하나인데요 나중에 어차피 이제 공부를 하게 되실 거예요

지금 간단히 설명드리면 큐는 어 이렇게 파이프 같이 생긴 자료구조로 보시면 돼요 그래서 이쪽으로

들어와서 이쪽으로 나가는데요 들어온 순서대로 이제 나가게 됩니다 그 예를 들어서 1번 2번 3번이 들어오면은

들어온 순서대로 1번 2번 3번 이나 이거랑 이제 반대 되는게 스택이 있어요 스택은 이제 8표 큐와 다르게 한쪽이 막혀 있는

자료구조로 보시면 돼요 그래서 들어온 곳으로 나가게 되겠죠 그러면 1번 2번 3번이 그러면 어떤

식으로 나가게 될까요? 예, 3번, 2번, 1번 뭐 이렇게 꺼꾸로 나가게 되겠죠. 그러면은 왜 왜 여기서 어 DFS 에서 Q 를

사용하게 된 거야? Q 를 사용하는 이유는 자 문제를 풀어보면 알 수가 있어요. 자, 일본에서 먼저 들어왔을 때 이번

5번을 여기에 들어오게 되거든요. 그 다음에 1번은 사라지게 돼요. 왜냐면 여기서 이제 확인을 했으니까. 그 다음은 입원을 확인을 하면서

3번이 들어오게 되구요. 우버 늘 확인하면서 5, 3번, 5번을 확인하면서 4번이 들어오게 돼요. 이런 식으로 휴 라는

자유 구조라 BFS 쓰라고 어 맡길 맡게 돼 있어요. 자, 그럼 거 꿀로 DFS 애쓰는 스텟 일을 맡게 돼 있거든요. 그리고

DFS 는 출항 받게 되었구요. 이거는 다 전에 천천히 다룰 게요. 자, 그래서 이제 이렇게 아이디어를 먼저 봤구요. 다음 시간 복잡도를

볼게요 시간 복잡도는 어 이 알고리즘이 얼마나 오래 걸려서 얼마나 오래 걸리는지 그래서 이제 1시간

안에 통화를 할 수 있는지를 보는 척도예요 시 간 복잡도는 크게 5가지로 표시하는데요 이게 비고

표기법이라고 해요 그래서 시간이 되시는 분들은 이거 분도 이제 따로 공부를 해 주시면 좋구요 b

국보 기법을 간단하게 말씀드리면 가장 최대의 시간을 뽑는 거예요 아이 이렇게 해서 가정 최대의 시간을

뽑아서 굉장히 그걸 간단하게 쭉 간략하게 해 가지고 얼마나 걸리는지 를 확인하는 거죠 왜냐 부분에 민희라

얇고 리즈 맨 이라는게 정확히 얼마가 걸리는 지를 정확하게 판단 힘들어요 그래서 비고 표기법으로 가늠한다 라고

보시면 될 것 같습니다 그러면 이제 BFS 에서는 버텍스 의 갯수 + 엣지 의 갯수 있었는데요 자 여기서 연산이 어떤 식으로

이루어지는지 알아볼게요 여기에 만약에 a b c d e f g 에 간선 의 이름이 있다고 해요 그러면 자 연산 에

어떤 식으로 할까요 1번 먼저 버텍스 에서 a 와 b 에 엣지 를 통해서 c 와 d 즉 2번과 5번 의 버텍스 가수가

될 거고요 그 다음에 d 와 f 의 연산의 있을 거예요 이런 식으로 버텍스 가다 계산 5 되고요 엣지 돋아

계산이 돼요 그래서 BFS 의 시간 복잡도는 버텍스 의 갯수 곱하기 엣지의 갯수를 보시면 되겠습니다

네 그러면 이제 자료 구조는 어떻게 쓰인 야 우선은 각각의 그래프가 어떻게 돼 있는지를 이 그래프에 대한

자료 구조가 먼저 있어야 돼요. 그 다음에 방문 여부를 확인할 수 있는 자료 구조가 있어요. 왜냐하면 내가 했던 곳을 제 방문하면 이제

중복해서 방문하게 되는 거니까 이미 방문을 했는지 안 했는지를 꼭 확인을 해 주셔야 되구요. 마지막으로 BFS 를 실행을 큐를

이제 Queue 가 필요하게 됩니다. 자 그러면 이제 기본 문제 DFS 기본 문제로 한번 풀어 보려고 하는데요. 우선은 100주년의 192

6번 26 문제를 풀 거에요. 이런 문제는 뭐 볼게요. 문제를 간단하게 제가 요약을 해자 며

이런 식으로 이제 그래프가 있는데요. 이렇게 그래프가 있는데요. 여기서 이제 이렇게 보이시나요? 이렇게 이렇게

이렇게 이렇게 1번 연속되어 있는 거에 개수를 세고요. 거기 중에 최대 값을 구하면 되는 거죠. 자 그럼 이건

어떻게 해 볼까요 우선은 i 뭐 아이디어 먼저 볼게요 그러니까 여기에서 보려고 하면 은 2일 보니

나왔을 때 여기에 연속해 있는 주변에 있는 1번 들을 기억 찾아 나가면 되겠죠 그럼 이 어 찾아나가는 거는

1번 들을 찾아 나가는 것은 bfs 하면 될 것 같아요 4 그래서 이 빙 지 아닌 지를 확인하고 1인 경우에는 더 이상 찾자

이룬 경우에만 찾아 나가는 거고 0일 때는 대상 찾지 않는 걸려요 자 그러면 그럼 여기서는 뭐 이렇게 찾을 수

있다고 제어 1 점에서는 그럼 여기에 넌 어떻게 하실까요 4 여기서부터 이 순서대로 계속 보모를 돌면서

어이 제비의 패스를 해나가면 되겠죠 그러면서 b 역 그래서 두 번째는 이중 포문을 들면서 홍 1이 나올 때마다

1이 나올 때마다 BFS 하면 되겠죠. 근데 여기서 중요한 건 뭐냐면 여기서 BFS 를 해서 한번 여기서 BFS 를 해서 한번 체크를

했다고 쳐 볼게요. 근데 여기서 시작을 했겠죠. 그러면 비자금 여기서는 BFS 해야 될 거야 아닐까요? 하면 안 되죠. 왜냐면 은 이미

한 번 봤습니까? 있나요? 그래서 이 중 후문에서 중요한 게 의 중포 문에서는 값이 1이어야 되고 그리고 이미 방문 안 돼 있는 곳에 아니에요. 이 두

개의 조건에서만 BFS 를 돌려야 되구요. 이렇게 해서 전체 끝까지 돌리면서 이때 이때 이제 이를 발견하면 은

전체 그림 개수를 올려줘야 되고 우리 여기서 그림 최대 값을 찾아 줘. 이런 식으로 문제를 풀어나가는 되겠습니다.

자, 그러면 한번 직접 후드를 잡으면서 1번 문제를 볼게요. 근데 그러면 이제 같이 코드를 짜 보려고 하는데요. 우선 제가 문제를

풀기 전에 뭐부터 해야 하죠? 예, 우선 세 가지를 먼저 보라고 했죠. 첫 번째는 아이디어

그리고 두 번째는, 두 번째는 시간 복잡도. 세 번째는 잘 해 보셔요. 자, 첫 번째 아이디어. 이중 포문을 돌면서 그리고

그래프가 값이 1이면 서로 연결되어 있는 거에 대해서 이제 BFS를 돌린 거구요. DFS를 돌면서

어, 각각 그린 갯수 + 1. 그리고, 그리고 최대값을 갱신해 줘야 되겠죠. 자, 이렇게 아이디어는 짜면 될 것

같아요. 자, 좀 시간 복잡도부터 생각해 볼까요? 전체 BFS의 시간 복잡도가 V + E라고 했죠. 동일하게 V를

느끼고, 인가를 켄지를 보면 되겠죠. 자, 그러면 부위가 몇 개인지 볼게요. 4 부위는, 에 곱하기 전체가 지금 N 곱하기 M

곱하기 n 이거든요 그럼 전체 이 각각 개수가 n개가 되겠죠 그러면 부위는 m 곱하기 n 이 있구요 그리고 여기서

이제 엣지의 재수는 여기서 각각 몇 개씩 연결해야 될까요 하나당 2개가 안되고 역에는 하나당 4개가

연결되어 좀 넉넉 잡아서 lg 는 부위 곱하기 2라고 내지 4라고 할게요 금호 5에 v 플러스 있는 지금

어 브이 v + 애 치 인데 이게 vdo 기사 보이죠 여기 카페 이거 사니까 그럼 우비가 되겠고요 5 9

5 곱하기 부위가 지금 여러분 입니까 애매 니 되겠죠 그럼 m2 지금 m 과 n 은 최대 500 이에요 도움말

500 곱하기 502 되겠죠 자 다시 볼게요 그러면 여기 500 곱하기 500 그리고 아까 여기 사업하기 오벨 곱하기 500

그럼 총을 쏠 것이죠 여기는 대충 몸 탐색 이후 보고 홍보 곳 그러면 약 100만 이정도 되겠네요 근데 이게 칙

1초에 연산 몇 번 할 수가 있죠 이 어깨를 알 수가 있죠 그러니까 2억을 이 어깨가 적으니까

문제를 풀 수 있겠네요 자금 자료구조 볼게요 에서 자료 건 후계 우선은 그래프 전체 지루가 있어야

될 거 같아요 그래서 이거는 약간 1 과 0 으로 이루어져 있으니까 2차원 배열 사용하면 될 것 같고요 그리고 밥은 여부는

어 방문했는지 블링 값으로 2차원 배열을 사용될 것 같아요 마지막으로 q 가 사용되는데 이것은 dfs 에서 사용이 될 것 같고요 자

그럼 문제를 풀어 볼게요 우선은 어 이건 습관 해주시는게 좋은데요 미드 씰 스 로 해서 링 톳은 ccs

사 안 저희 드 여기는 습관 해주신 데 좋아 이게 뭐냐 가 이틀 역 덜 빠르게 해주는

흐르 거든요 이 풀려 기가 욕 되게 큰 경우에는 문제가 되고 오래 걸리는 경우가 있어요 그래서 이렇게 습관을 해주는

것이 좋구요 그런 문제를 계속 들어갈게요 우선 m 과 m m1 자주 무엇이죠 뎅 과잉을 텐트 김프 자 이게 어느

부분이 있냐면 여 부분이에요 m 과 m 과 m 그리고 앞으로 nj 에 줄에 대해서 이 젬 걔가 데이터가 들어올 거에요

자 그러면 그 전체 지도는 2g 을 지루는 어 얘 왜 인터넷 게임 뜻을 스플릿 수리해서 인테리어를 바꿔주고 요 그리거 를

리스트 로 바꿔 준 다음에 이것을 몇 개가 필요하죠 이렇게 된게 n 개의 줄이 필요 하게 되겠네요 그 다음에 방 번의 쏘는 좀

paul's 가 가루를 느껴져 내 뭉개 부려 이게 세로 도 엥겔 가 있어야 됐네요 이렇게 해서 우선은 기본적인 자료

구조를 만들어 봤구요 자 이제 이 중 풍물 한번 더 알아볼게요 좀 와 보통 이중 폼 할 때는 y 를

먼저 들고 x 를 덮는 식으로 할게요 해요 자 ange y y 를 먼저 돌면서 100회를 도는데 이때 이제

값이 이면서 방문하지 않은 키에 패스를 돌려고 있죠 자 그러면 값이 이프 값이 값이 리면서 그리고 방북 체크 해당 왕

코딩테스트 알고리즘 - 1. BFS

개발자 장고

소개 및 그래프 탐색 개념 설명

코딩 테스트 첫 번째 시간, BFS(너비 우선 탐색) 시작

BFS는 그래프 탐색의 한 방법, 그래프 탐색이란 연속된 요소들을 모두 확인하는 방법

그래프 탐색 예시: 그래프의 요소들을 순차적으로 확인하는 과정

버텍스(Vertex)와 엣지(Edge) 개념 설명

그래프 탐색의 활용 예시: 왕 찾기, 개수 세기 등

BFS(너비 우선 탐색): 너비를 먼저 탐색, DFS(깊이 우선 탐색): 깊이를 먼저 탐색

BFS 탐색 순서: 자기 자식 노드들을 먼저 탐색 후, 다음 자식 노드의 자식 노드들을 탐색

DFS 탐색 순서: 자식 노드의 자식 노드를 먼저 탐색, 자식이 없으면 위로 올라가 다음 자식 노드 탐색

BFS 예제를 통한 탐색 순서 설명

DFS 예제를 통한 탐색 순서 설명

BFS 코드 구현: 연결된 버텍스들을 큐(Queue)에 저장하고, 가장 앞의 값을 꺼내 반복 처리

큐(Queue) 자료구조 설명: FIFO(First-In, First-Out)

스택(Stack) 자료구조 설명: LIFO(Last-In, First-Out)

BFS에서 큐를 사용하는 이유 설명

시간 복잡도: 알고리즘의 실행 시간 측정

시간 복잡도 표기법: 빅오(Big O) 표기법

빅오 표기법: 최대 시간을 기준으로 알고리즘의 시간 복잡도를 간략하게 표현

BFS 시간 복잡도: V(Vertex) + E(Edge)

필요한 자료구조: 그래프 자료구조, 방문 여부 확인 자료구조, 큐(Queue)

기본 문제(10000번, 1926번): 그래프에서 연속된 1의 개수를 세고 최댓값 구하기

BFS 활용 조건: 1인 경우에만 탐색, 0인 경우는 탐색하지 않음

중복 탐색 방지: 이미 방문한 노드는 다시 탐색하지 않음

코드 구현 및 시간 복잡도 분석

코드 구현 전 고려 사항: 아이디어, 시간 복잡도, 자료구조

아이디어: 이중 반복문과 BFS 활용

시간 복잡도 분석: V + E, V는 정점 개수, E는 간선 개수

문제의 V와 E 계산: N x M (정점), N x M x 4 (간선)

최악 시간 복잡도 계산: 약 100만

자료구조: 2차원 배열(그래프), 2차원 배열(방문 여부), 큐(Queue)

코드 최적화: 미리 계산하여 반복문 횟수 줄이기

입력 데이터 처리: 스트림을 이용한 데이터 변환

이중 반복문 구현: y축 우선 순회

BFS 함수 구현: 방문 여부 체크 및 그림 크기 계산

변수 선언: 그림 개수, 최대 크기

큐가 빌 때까지 반복: 큐에서 요소를 꺼내 주변 탐색

주변 탐색: 상하좌우 탐색 및 방문 여부 확인

테스트 코드 실행 및 결과 확인