DFS, BFS 개념을 공부해도 실제로 코딩 하는 것이 쉽지 않다.
실전 문제를 통해 연습해보기
음료수 얼려먹기
출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬
문제 설명
N × M 크기의 얼음틀이 있다. 구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.
입력 조건
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1000)
- 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
출력 조건
- 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.
예시
입력
4 5
00110
00011
11111
00000출력
3알고리즘 이해 없이 구현으로만 해결하려 하면 아무리 시간을 쏟아도 해결이 안 된다.
DFS 풀이
내 풀이
# 음료수 얼려먹기 DFS
n, m = map(int, input().split())
ice = []
for i in range(n):
ice.append(list(map(str, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [ [False] * m for _ in range(n) ]
answer = 0
def dfs(x, y):
global chk
if x < 0 or x >= n or y < 0 or y >= m or visited[x][y] or ice[x][y] == '1':
return
else:
chk = 1
visited[x][y] = True
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
dfs(nx, ny)
for i in range(n):
for j in range(m):
chk = 0
dfs(i, j)
if chk == 1:
answer += 1
print(answer)책 풀이
# 음료수 얼려먹기 DFS (책)
# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 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
# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
result += 1
print(result) # 정답 출려개선점
global chk같은 거 할 필요 없이, 최초 동작 함수에서return True해주면 쉽게 카운트 가능visited같은 리스트 추가 생성 없이, 기존 graph 값을 수정하는 방식으로도 방문 처리 가능
BFS 풀이
내 풀이
# 음료수 얼려 먹기 - BFS
from collections import deque
n, m = map(int, input().split())
ice = []
for i in range(n):
ice.append(list(map(str, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [ [False] * m for _ in range(n) ]
answer = 0
def bfs(x, y, visited):
queue = deque([(x, y)])
chk = 0
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<m and not visited[nx][ny] and ice[nx][ny] == '0' :
visited[nx][ny] = True
queue.append((nx, ny))
chk = 1
if chk == 1:
return 1
else:
return 0
for i in range(n):
for j in range(m):
answer += bfs(i, j, visited)
print(answer)타인 풀이
# 음료수 얼려먹기 - BFS - 타인 코드
from collections import deque
n, m = map(int, input().split())
# 그래프 생성
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 상하좌우 탐색
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# BFS
def bfs(x, y):
# 현재 위치를 큐에 집어넣음
q = deque()
q.append((x,y))
# 만약 현재 위치가 1이라면 아이스크림을 만들 수 없는 공간이거나 이미 탐색한 곳이므로 False 반환
if graph[x][y] == 1:
return False
# 현재 위치를 기준으로 BFS 탐색
while q:
x, y = q.popleft()
# 현재 위치 값을 0에서 1로 변경
graph[x][y] = 1
# 상하좌우 탐색
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 얼음 틀 범위에서 벗어나지 않으면서 그 위치의 값이 0인 경우에만 큐에 집어넣음
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
q.append((nx,ny))
# 하나의 아이스크림이 만들어지는 공간을 모두 탐색한 경우 True
return True
cnt = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 BFS 수행
if bfs(i, j) == True:
cnt += 1
print(cnt)개선점
- 마지막에
return True넣는 걸로 카운트 쉽게 가능
Statistics & Data Science