코테 연습) 그래프탐색 알고리즘 : DFS/BFS(DFS 문제 : 음료수 얼려 먹기).python
q1) 음료수 얼려먹기
- N * M 크기의 얼음 틀이 있다 구멍이 뚫려있는 부분은 0 칸막이가 존재하는 부분은 1로 표시
구멍이 뚫려 있는 부분까리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주
이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수는?
4 * 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다
- 문제의 유형은 연결요소 찾기 즉 커넥티드 컴포넌트라고 볼 수 있다
- 이 문제는 DFS혹은 BFS로 해결 할 수 있다
- 얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다
- 상, 하, 좌, 우로 연결된 포인트는 서로 인접한 노드 현태로 표현할 수 있다
맨 왼쪽 상단의 0을 기준으로 인접한 노드를 구해놓고 1을 제외하고 방문하지 않은 노드를 찾는 방식으로 문제를 해결하면 될 것 같다
- 특정 지점의 주변 상, 하, 좌, 우를 살펴본 뒤 주변 지점에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문
- 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복하면 연결된 모든 지점 방문
- 모든 노드에 대하여 위의 과정을 반복하여 방문하지 않은 지점의 수를 카운트
->입력창
# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):
# 주어진 범위를 벗어나는 경우에는 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
# 현재 노드를 아직 방문하지 않았다면
if graph[x][y] == 0:
# 해당 노드 방문 처리
graph[x][y] = 1
# 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
dfs(x - 1, y)
dfs(x, y - 1)
dfs(x + 1, y)
dfs(x, y + 1)
return True
return False
# N, M을 공백을 기준으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
result += 1
print(result) # 정답 출력
->출력창 4 * 5행렬을 만들기 위해 n m값 4 5를 공백을 두고 엔터, 앞 행렬의 행과 열만큼의 2차원 리스트를 만들기 위해
00110 앤터 00011 엔터 11111 엔터 00000엔터 출력 3
C:\Users\admin\PycharmProjects\ML_EX\venv\Scripts\python.exe C:/Users/admin/PycharmProjects/ML_EX/study05.py
4 5
00110
00011
11111
00000
3
종료 코드 0(으)로 완료된 프로세스
풀이)
# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):
# 주어진 범위를 벗어나는 경우에는 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
- x, y 함수를 만든다 만약 x가 -보다 작거나 같거나 x가 n보다 크거나 같거나 y가 -1보다 작거나 같거나 y가 m보다 크거나 같으면 종료 그렇지 않은경우 아래 조건문을 수행
# 현재 노드를 아직 방문하지 않았다면
if graph[x][y] == 0:
- 현재 노드를 아직 방문하지 않았다면 아래 조건을 수행
# 해당 노드 방문 처리
graph[x][y] = 1
- 제시한 바가 없으니 가장 작은 수 0,0부터 방문해서 0,0은 이제 방문처리를 한다
# 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
dfs(x - 1, y) # 좌(0,0 넣었을 때)
dfs(x, y - 1) # 하(0,0 넣었을 때)
dfs(x + 1, y) # 상(0,0 넣었을 때)
dfs(x, y + 1) # 우(0,0 넣었을 때)
return True
4행 5열을 기준으로 상 하 좌 우를 살펴보자 0,0기준 우(0,1), 하(1,0)는 0이므로 방문하지 않은 인접노드가 된다
| 0(0,0) | 0(0,1) | 1(0,2) | 1(0,3) | 0(0,4) |
| 0(1,0) | 0(1,1) | 0(1,2) | 1(1,3) | 1(1,4) |
| 1(2,0) | 1(2,1) | 1(2,2) | 1(2,3) | 1(2,4) |
| 0(3,0) | 0(3,1) | 0(3,2) | 0(3,3) | 0(3,4) |
- 첫번째 x,y에 0,0을 대입 했을 때 좌(-1,0), 하(0,-1)는 -1이 있으므로 종료, 우(1,0), 상(0,1)은 방문처리
| 1(0,0) | 1(0,1) | 1(0,2) | 1(0,3) | 0(0,4) |
| 1(1,0) | 0(1,1) | 0(1,2) | 1(1,3) | 1(1,4) |
| 1(2,0) | 1(2,1) | 1(2,2) | 1(2,3) | 1(2,4) |
| 0(3,0) | 0(3,1) | 0(3,2) | 0(3,3) | 0(3,4) |
- 다시 반복문 을 1,0과 0,1중에 작은 수 부터 차례로 방문하지 않은 노드부터 방문처리
- 잘 모르지만 작은 수로 따졌을 때 우(0,1)과 하(1,0)에서 x가 우선이니까 0,1이 작은거 같아서 0,1 노드부터 상, 하, 좌, 우 방문
- 위 재귀적 호출에서 0,1 대입해보면
좌(-1,1)는 -1이 있으니까 종료 나며지 하(0,0), 우(0,2)는 이미 1이므로 방문노드이고 나머지 방문하지 않은 노드 상(1,1)에 방문해서 방문처리 이제는 0,0근방에 방문하지 않은 노드기 없으니
| 1(0,0) | 1(0,1) | 1(0,2) | 1(0,3) | 0(0,4) |
| 1(1,0) | 1(1,1) | 0(1,2) | 1(1,3) | 1(1,4) |
| 1(2,0) | 1(2,1) | 1(2,2) | 1(2,3) | 1(2,4) |
| 0(3,0) | 0(3,1) | 0(3,2) | 0(3,3) | 0(3,4) |
- 이제 1,1 대입해서 방문하지 않은 노드 방문 표에서 좌(0,1), 하(1,0), 상(2,1)은 이미 방문노드이고 우(1,2)만 방문하지 않은 노드이므로 방문처리
| 1(0,0) | 1(0,1) | 1(0,2) | 1(0,3) | 0(0,4) |
| 1(1,0) | 1(1,1) | 1(1,2) | 1(1,3) | 1(1,4) |
| 1(2,0) | 1(2,1) | 1(2,2) | 1(2,3) | 1(2,4) |
| 0(3,0) | 0(3,1) | 0(3,2) | 0(3,3) | 0(3,4) |
- 그다음 1,2를 대입해보면 좌(0,1), 하(1,0), 상(2,2), 우(1,3) 모두 방문노드이므로 이제 리턴값이 True가 아님 아래처럼
return False
- 종료하고 (현재 위치가 처음위치(0,0)에서 처음 dfs가 수행이 된 것이기 때문에 그 위치(0,0)에 대해서 아래 for문 아래 result값을 증가시킨다)
# N, M을 공백을 기준으로 구분하여 입력받기
n, m = map(int, input().split())
- 공백을 기준으로 행열값 입력받기
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
- 행값을 0부터 n-1까지 차례로 꺼낸거를 i라는 변수로 두고 아래 조건문 반복
graph.append(list(map(int, input())))
- n줄에 걸쳐서 2차원 리스트 맵정보를 입력받는다 즉 입력받은 n줄을 그래프 리스트에 채워준다
- 이때 입력은 공백없이 0과 1로 구성된 문자열 형태(맨위에 조건 제시해줌 " if x <= -1 or x >= n or y <= -1 or y >= m:")로 주어지기 때문에 한줄로 입력받은 다음 각 원소를 정수형으로 변환해주고 리스트로 만든다 그럼 이제 모든 원소가 0 혹은 1인 정수 리스트가 만들어진다
# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
- 이제 리스트형태로 되어 있는 행값을 0부터 n-1까지 차례로 꺼낸거를 i라는 변수로 두고 아래 조건문 반복
for j in range(m):
- 리스트형태로 되어있는 열값을 0부터 m-1까지 차례로 꺼낸거를 j라는 변수로 두고 아래 조건문 반복
- n * m 위치에서 dfs를 실행 0,0에서 실행하고 1,2에서 종료되었으니 DFS는 0,0으로 시작이 되었으므로
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
result += 1
- 0,0지점에서 result값이 +1이 되는거 (0,0부터 인접 노드들을 1로 만든 한 뭉텅이가 하나로 카운팅된다)
(현재 위치에 대해서 이번에 dfs를 수행해서 처음 방문처리가 되었다면 그 때 카운트(+1) 진행)
- 표에서 보면 다음 반복문의 시작은 0,4 그 다음 반복문의 시작은 3.0으로
print(result) # 정답 출력
- result값은 3이 된다!
출처 / 유튜브 [동빈나 - (이코테2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬]