Untitled

Fold the Video

Loading...

20강 DFS & BFS 기초 문제 풀이-0
20강 DFS & BFS 기초 문제 풀이-1

dfs 와 bfs

음료수 얼려먹기 문제 문제내용을 읽어볼게요

20강 DFS & BFS 기초 문제 풀이-4
20강 DFS & BFS 기초 문제 풀이-5
20강 DFS & BFS 기초 문제 풀이-6

행이 4 열이 5라고 볼수 있겠죠

현재 예시는 4 곱하기 5 즉 행이 4고 열이 5인 크기라고 볼 수 있겠네요

20강 DFS & BFS 기초 문제 풀이-9
20강 DFS & BFS 기초 문제 풀이-10

입니다

20강 DFS & BFS 기초 문제 풀이-12
20강 DFS & BFS 기초 문제 풀이-13

전부다 음료수를 부어가지고

음료수를 붙는다면 서로 연결되어있기 때문에 이렇게

20강 DFS & BFS 기초 문제 풀이-16

5개를 묶어서 또한 한덩이가 만들어지 겠네요

20강 DFS & BFS 기초 문제 풀이-18
20강 DFS & BFS 기초 문제 풀이-19
20강 DFS & BFS 기초 문제 풀이-20
20강 DFS & BFS 기초 문제 풀이-21

새로길이인 N과 가로길이인 M이 주어지고요 이때 n과 m은 천이하에 크기때문에

전체 얼음틀에 공간은 100만개이하게 되겠습니다

이외에

20강 DFS & BFS 기초 문제 풀이-25

형태가 주어진다고

20강 DFS & BFS 기초 문제 풀이-27

얼음틀이 볼수 있습니다

20강 DFS & BFS 기초 문제 풀이-29

결과적으로 우리는 출력하면 됩니다

자 그럼 각자 이문제를 풀어본 뒤에 자신만의 코드로 표현해보세요

20강 DFS & BFS 기초 문제 풀이-34

20강 DFS & BFS 기초 문제 풀이-36
20강 DFS & BFS 기초 문제 풀이-37

dfs 혹은 dfs를 이용해서 연결요소의 개수가

20강 DFS & BFS 기초 문제 풀이-39

형태로 주어졌다고 하면 이와 같이

20강 DFS & BFS 기초 문제 풀이-41
20강 DFS & BFS 기초 문제 풀이-42

각위치에서 인접한 노드인것처럼

20강 DFS & BFS 기초 문제 풀이-44

dfs나 bfs를 이용

20강 DFS & BFS 기초 문제 풀이-46
20강 DFS & BFS 기초 문제 풀이-47

방문처리 될겁니다

20강 DFS & BFS 기초 문제 풀이-49

그러면 자연스럽게 총3개가 존재하는 이연결요서만 전부 방문 처리해야 될겁니다

20강 DFS & BFS 기초 문제 풀이-51

우리는 전체연결 요소가 몇개인지 계산할 수 있습니다

20강 DFS & BFS 기초 문제 풀이-54
20강 DFS & BFS 기초 문제 풀이-55

살펴본 뒤에

20강 DFS & BFS 기초 문제 풀이-57
20강 DFS & BFS 기초 문제 풀이-58

방문을 진행하는 과정을 반복하면

20강 DFS & BFS 기초 문제 풀이-60

다시말해서 dfs를 이용해서

인접한 노드에 대해서도 dfs를

20강 DFS & BFS 기초 문제 풀이-63

모든 노드를

칸막이로 노드들은 전부 방문하게 되겠죠

20강 DFS & BFS 기초 문제 풀이-66

지점에 수를 카운트

20강 DFS & BFS 기초 문제 풀이-69

20강 DFS & BFS 기초 문제 풀이-72

n과 m을 입력 받구여

20강 DFS & BFS 기초 문제 풀이-74

공백 구분 없이 문자열 형태로 주어지기 때문에 이렇게 한줄을 입력받은 다음에 각 원소를

정수형으로 바꿔서 다시 리스트 형태로 만들어줍니다

20강 DFS & BFS 기초 문제 풀이-77
20강 DFS & BFS 기초 문제 풀이-78

각 위치에서 dfs

2번의 dfs를 수행해서

20강 DFS & BFS 기초 문제 풀이-81

자 실제로 dfs를 확인해 보시면은요 이렇게 주어진 범위를 벗어나는 경우에는

종료될수 있도록 하고 이제 그렇지 않은 경우의 현재위치를 아직 방문하지 않았다면

이제 방문처리를 하는겁니다 그다음에 이제

20강 DFS & BFS 기초 문제 풀이-85

결과적으로 ture값을 반환하도록 해서 현재 위치에 대해서 처음 dfs가 수행된것이기 때문에 그 위치에 대해서 이 result 값을 증가 시킵니다

20강 DFS & BFS 기초 문제 풀이-87

모두 재귀적으로 dfs를 호출합니다

20강 DFS & BFS 기초 문제 풀이-89

이런식으로 상하 좌우에 대해서

20강 DFS & BFS 기초 문제 풀이-91

목적으로만 수행됩니다

정리

처음 dfs 호출 될때만 트루값이 1을 나오게만 하고

나머지 상하좌우 확인하는 dfs는 그냥 방문 처리 목적만 있는 것임

20강 DFS & BFS 기초 문제 풀이-98
20강 DFS & BFS 기초 문제 풀이-99

이 리절트 값을 증가시키는걸 확인할수 있습니다

20강 DFS & BFS 기초 문제 풀이-101

dfs를 이용해서

20강 DFS & BFS 기초 문제 풀이-103
20강 DFS & BFS 기초 문제 풀이-104

c++

20강 DFS & BFS 기초 문제 풀이-106

마다 음료수 틀 정보가 주어질때

20강 DFS & BFS 기초 문제 풀이-108

%1d라고 입력을해서

20강 DFS & BFS 기초 문제 풀이-110
20강 DFS & BFS 기초 문제 풀이-111

파이썬과 정확인 동일한 걸

현제 레버로 주어질수 있는 최대크기가 천곱하기 천이기 때문에 이와같이 미리 전체 그레프를 크게 설정을 해서 입력받을때 문제 없도록 처리하고 있습니다.

20강 DFS & BFS 기초 문제 풀이-115
20강 DFS & BFS 기초 문제 풀이-116

M을 입력받은 뒤에 그다음부터 문자열 형태로 데이터를 입력받기 때문에 버퍼를 지우고 입력받기를 시작합니다 그래서 하나의 문자열을 입력을 받은뒤에각 문자를 하나씩 확인하면서 거기에서 문자 0의 아스키 코드값을 빼주어서 결과적으로 0혹은 1의 정수형 데이터가 2차원 리스트에 담길수 있도록합니다

20강 DFS & BFS 기초 문제 풀이-119

이후의 모든 dfs를 호출해서 dfs에 반환된 값이 ture값이라면 카운트

20강 DFS & BFS 기초 문제 풀이-122

dfs 코드를 확인해보시면

20강 DFS & BFS 기초 문제 풀이-124

수행한 뒤에 ture값을 리턴

20강 DFS & BFS 기초 문제 풀이-126

대해서 방문처리를 수행할수 있도록합니다

20강 DFS & BFS 기초 문제 풀이-128

결과적으로 dfs를 호출해서 ture 값이

20강 DFS & BFS 기초 문제 풀이-131
20강 DFS & BFS 기초 문제 풀이-132
20강 DFS & BFS 기초 문제 풀이-133
20강 DFS & BFS 기초 문제 풀이-134

20강 DFS & BFS 기초 문제 풀이-136

미로의 출구는 N,M위치의 존재

이때 괴물이 있는 부분은 0으로 괴물이 없는 부분은 1로 표시

20강 DFS & BFS 기초 문제 풀이-139

하는데요 탈출하기위해

움직여야하는 최소칸의 개수를 구하는것이

20강 DFS & BFS 기초 문제 풀이-142

셀때는 시작칸과 마지막칸을 모두 포함해서 구할수 있도록 합니다

20강 DFS & BFS 기초 문제 풀이-144

20강 DFS & BFS 기초 문제 풀이-146

전체 맵의 크기는 최대 200X200이라고 할 수 있겠구요

20강 DFS & BFS 기초 문제 풀이-148

정수가 미로의 정보로서 주어짐

20강 DFS & BFS 기초 문제 풀이-150

가장 왼쪽 위 위치에서

20강 DFS & BFS 기초 문제 풀이-152
20강 DFS & BFS 기초 문제 풀이-153

코드로 문제를 풀어주세요

20강 DFS & BFS 기초 문제 풀이-155

미로탈출문제 해결 아이디어는 다음과 같습니다

bfs를 수행하는 건데요 이bfs는 간선의 비용이 모두 같을때 최단거리를

20강 DFS & BFS 기초 문제 풀이-158

노드를 탐색하기 때문인데요

20강 DFS & BFS 기초 문제 풀이-160

이때 상하좌우로 연결된 모든 노드는

그래서 가장 왼쪽 위 지점이라고 할수 있는 일컴마일에 위치해서

20강 DFS & BFS 기초 문제 풀이-164

bfs를 수행해서 모든 노드에대한

20강 DFS & BFS 기초 문제 풀이-166
20강 DFS & BFS 기초 문제 풀이-167

같이 상하 좌우 위치에 존재하는 노드들이 인접노드로서 표현되는걸 확인할 수 있습니다.

20강 DFS & BFS 기초 문제 풀이-169
20강 DFS & BFS 기초 문제 풀이-170

1 ,1에 위치해서 bfs를 수행

20강 DFS & BFS 기초 문제 풀이-172

노드중에서 값이 1인 노드

큐에 원소를 넣어서 초기원소의 값이1인 경우에 한에서만 bfs를 진행합니다

20강 DFS & BFS 기초 문제 풀이-175

노드를 방문하게 되고 이제 이노드까지의

그이유는 본 문제에서는 시작위치와 마지막 위치를 포함해서 마지막 위치까지 도달하는 최단경우에 포함되어 있는 노드의 수를 출력해야 되기 때문에 이 노드 까지는 거리가 2라고 할수 있는겁니다

20강 DFS & BFS 기초 문제 풀이-179

이 노드또한 q에 담기게 되고 다시 이노드를 꺼낸 다음에 마찬가지로

인접한 노드인 이 노드까지 방문을 수행하게 됩니다

20강 DFS & BFS 기초 문제 풀이-182

이노드를 q에 넣을때 방문처리를 수행한뒤에 이노드 까지는 거리가 3인것으로 기록을 하는 방식으로 매번

20강 DFS & BFS 기초 문제 풀이-184

최단거리의 1을 더한 값을 기록할 수 있도록 합니다

20강 DFS & BFS 기초 문제 풀이-186

시작 위치에서 bfs를 수행했을때 다음과 같이 최단 경로의 값들이

1식 증가하는 형태로 변경되고

결과적으로 마지막 위치에 기록되어 있는 최단 거리 값을 출력하도록 만들면 정답

20강 DFS & BFS 기초 문제 풀이-190

정답 판정을 받을수 있습니다

20강 DFS & BFS 기초 문제 풀이-192
20강 DFS & BFS 기초 문제 풀이-193
20강 DFS & BFS 기초 문제 풀이-194

입력을 받습니다

20강 DFS & BFS 기초 문제 풀이-196

대해서 int 형으로 바꾸어서 다시 리스트로 만드는 방법을 사용합니다 그래서

이렇게 그래프를 초기화 한 뒤에 이제 네가지 방향 즉 상하좌우로 이동할수 있기 때문에

이와 같이 방향백터를 정의해주고여

그다음에 bfs함수를 호출하는데요 bfs함수는 바로 다음과 같이

20강 DFS & BFS 기초 문제 풀이-201

뎃 라이브러리를

20강 DFS & BFS 기초 문제 풀이-203

이루어진 튜플 데이터를 그래서 이제 q가 bfs를 수행하는데요

20강 DFS & BFS 기초 문제 풀이-205

큐에서

연결된 위치가 공간을 벗어난다면 무시할수 있도록 하고 또한 괴물이

20강 DFS & BFS 기초 문제 풀이-208
20강 DFS & BFS 기초 문제 풀이-209

해당 노드를 처음 방문 최단거리를

20강 DFS & BFS 기초 문제 풀이-211

에서의 최단거리 값의 1을 더한 값을

20강 DFS & BFS 기초 문제 풀이-214

같이 큐에 데이터를 넣으면서

20강 DFS & BFS 기초 문제 풀이-216

최단거리를 반환하면 정답

20강 DFS & BFS 기초 문제 풀이-218
20강 DFS & BFS 기초 문제 풀이-219

c++

파이썬과 동일한

실제로는 이 bfs 함수가 이 메인함수 위쪽에 들어가야합니다

20강 DFS & BFS 기초 문제 풀이-223

전체코드는 깃허브에서 확인해주세요

자 스래서 그래프로 2차원 형태의 배열을 만들어주고

20강 DFS & BFS 기초 문제 풀이-226

배열을 이용해서 상하좌우 방향을 기록할수 있도록 했고요

이제 마찬가지로

20강 DFS & BFS 기초 문제 풀이-229

전체 맵에 대한 정보가

이렇게 숫자나 싯데이터를

20강 DFS & BFS 기초 문제 풀이-233

bfs를 호출

20강 DFS & BFS 기초 문제 풀이-235

쌍을 입력받기위해서 페어객체(q)를 이용합니다

구조체나 클래스를 정의하지 않고도 간단히 데이터의 쌍을 표현할수 있습니다

20강 DFS & BFS 기초 문제 풀이-238

q에 넣을수 있도록 하구요

20강 DFS & BFS 기초 문제 풀이-240

큐가

원소를 하나씩 꺼낸뒤에

20강 DFS & BFS 기초 문제 풀이-243
20강 DFS & BFS 기초 문제 풀이-244

무시하고요 이제 해당 노드를 처음 방문할때만 최단거리값이 기록될 수 있도록 합니다

그래서 이전

20강 DFS & BFS 기초 문제 풀이-248

최단거리 값

20강 DFS & BFS 기초 문제 풀이-250

이 그래프 배열의

20강 DFS & BFS 기초 문제 풀이-252

bfs를 실행한

최단거리를 반환할수 있도록하면 마찬가지로 정답 판정을 받을수 있습니다

20강 DFS & BFS 기초 문제 풀이-255

깃허브에서

Last Updated:

Summarize & share videos seamlessly

Loading...