수리링의 데이터교실

graph_45 = [
    [0,0,1,1,0],
    [0,0,0,1,1],
    [1,1,1,1,1],
    [0,0,0,0,0]
]

n = 4
m = 5

첫째 / BFS 방식으로 풀기

출발점에서부터 점진적으로 진행해가는 방식으로 접근하는 경우 BFS를 고려해볼 수 있습니다.

일단 BFS니까 아묻따 디큐부터 임포트해주고 시작합니다.

from collections import deque

1. 함수를 작성합니다. 입력받은 출발점 좌표로부터 시작하여 출발점 좌표가 1이면 바로 False를 리턴하고, 출발점 좌표가 0이면 주변을 탐색하면서 0이 있으면 1로 바꾸고, 더이상 바꿀 0이 없는 경우에는 True를 리턴하는 함수를 작성합니다.

2. 함수 작성 이후, 주어진 그래프의 (0, 0)부터 시작하여 n*m 좌표마다 함수를 적용하도록 이터레이션을 돌립니다. True가 반환되는 갯수가 곧 음료수 얼음 덩어리의 갯수가 됩니다.

def ice_bfs(row_init, col_init):
    # 만약 주어진 좌표가 0이라면 가보자고!
    if graph[row_init][col_init] == 0:
        q = deque([[row_init, col_init]])
        # ---------------------------------------- 무한 루프 
        while True:
            if not q:
                return 1

            row, col = q.popleft()
            for [dx, dy] in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
                # 이동한 값이 지도 안에 있고
                if 0 <= row + dx < n and 0 <= col + dy < m:
                    # 얼릴 수 있다면
                    if graph[row+dx][col+dy] == 0:
                        # 1번 도장을 찍고, 그 다음 할일 추가하세요
                        graph[row+dx][col+dy] = 1
                        q.append([row+dx, col+dy])
        # ---------------------------------------- 무한 루프 
    else:
        return 0

result = 0

for row in range(n):
    for col in range(m):
        result += ice_bfs(row, col)

print(result)
# 3

둘째 / DFS 방식으로 풀기

위에서 작성한 함수를 DFS방식을 활용한 재귀함수로 바꾸어 작성해 봅시다. (같은 기능!)

def dfs_recursive(row, col):
    # 주어진 점이 틀 밖이라면 바로 함수 종료
    if row <= -1 or row >= n or col <= -1 or col >= m:
        return False
    
    # [1] 주어진 점이 0이라면 True를 반환
    if graph[row][col] == 0:
        
        graph[row][col] = 1  # 일단 True 반환 전에 0->1로 바꾸고
        dfs_recursive(row, col-1)
        dfs_recursive(row-1, col)
        dfs_recursive(row, col+1)
        dfs_recursive(row+1, col) # 상하 좌우도 전부 점검해주기!

        return True

    # [2] 주어진 점이 1이라면 False를 반환
    else:
        return False

같은 방식으로 모든 좌표점에 작성한 함수를 돌려주면서 True가 반환되는 개수를 세어 주면 끝~

result = 0

for row in range(n):
    for col in range(m):
        result += dfs_recursive(row, col)

print(result)
# 3

짱짱 재밌군!

BFS도 DFS도 자유자재로 활용할 수 있도록 열심히 반복!

다음 문제로는 카카오 2022 블라인드 공개채용 <양과 늑대> 문제를 풀어봅시다...

백준 2178번 미로탐색

https://www.acmicpc.net/problem/2178

n = 4
m = 6

graph = [
	[1, 0, 1, 1, 1, 1],
 	[1, 0, 1, 0, 1, 0],
 	[1, 0, 1, 0, 1, 1],
 	[1, 1, 1, 0, 1, 1]
 ]

0과 1로 이루어진 n * m 크기의 미로 그래프가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

먼저 상하좌우로 움직일수 있는 x, y 델타값을 리스트로 작성한다.

def dfs_escape(start = (0, 0)):
	# x, y의 현재 포지션을 정해 준다. 
    x_pos = start[0]
    y_pos = start[1]
    
    # 할 일을 기록할 디큐 리스트 q를 작성한다.
    q = deque()
    
    # 가장 처음 초기값을 세팅해준다. x, y의 좌표값 위치를 튜플로 집어넣는다.
    q.append((x_pos, y_pos))
    
    # 할 일이 없을 때까지 반복!
    while q:
    	now_x, now_y = q.popleft()
        
        # 상하좌우 4번 반복
        for i in range(4):
        	next_x = now_x + dx[i]
        	next_y = now_y + dy[i]
            
            # 만약 다음으로 갈 좌표값이 미로를 벗어나지 않는다면
            if 0 <= next_x < n and 0 <= next_y < m:
                if graph[next_x][next_y] == 1:
                    graph[next_x][next_y] = graph[now_x][now_y] + 1
                    q.append((next_x, next_y))

bfs_miro()


graph
# [[3, 0, 9, 10, 11, 12],
#  [2, 0, 8, 0, 12, 0],
#  [3, 0, 7, 0, 13, 14],
#  [4, 5, 6, 0, 14, 15]]


graph[n-1][m-1]
# 15

https://www.acmicpc.net/problem/18352

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다. 

[ 입력 조건 ] 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

[출력조건] X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다. 이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

예시 2번으로 문제를 풀어보자.

n, m, k, x = map(int , input().split())
# 4 4 1 1


graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input("출발 도착").split())
    graph[a].append(b)
    
    
graph
# [[], [2, 3], [3, 4], [], []]

먼저 입력을 받아 n, m, k, x값을 할당받고,

graph 리스트를 만들어 각 도시별로 연결된 도시들을 표시해준다.

INF = float("inf")
[INF] * (n + 1)
# [inf, inf, inf, inf, inf]

앞으로 출발 도시 x로부터 각각의 모든 도시까지 거리를 distance로 계산해줄 것이다.

(n+1)을 곱해주는 이유는 가상의 0번 도시를 설정하여 인덱스를 편하게 계산해주기 위함이다.

앞으로 distance에서 자기 자신과의 거리는 0으로, 자기 자신을 제외한 다른 도시는 모두 INF로 시작하는 점을 기억하자.

def solution(start):
    # 앞으로 방문해야할 도시 리스트는 디큐 리스트 q로 둔다.
    q = deque()
    # 출발점 도시 x로부터의 거리를 나타내는 디큐 리스트 distance를 만든다.
    distance = deque([INF] * (n+1))
    
    # 초기값 세팅
    q.append(start)
    distance[start] = 0
    
    # 더이상 방문할 도시가 없을 때까지 반복하기
    while q:
    	# 지금 방문하는 도시 now
    	now = q.popleft()
        for next_city in graph[now]:
        	# 만약 아무도 오지 않았던 신규 방문지라면
            if distance[next_city] == INF:
            	# 본 문제에서는 도시간의 거리가 1이므로 1을 더하지만
                # 문제 조건 따라 1이 아니게 될 수 있음
            	distance[next_city] = distance[now] + 1
                q.append(next_city)
                
     # 디스턴스 리스트를 리턴
     return distance

dis_result = bfs_city(x)
dis_result
# deque([inf, 0, 1, 1, 2])

dis_k = [i for i, v in enumerate(dis_result) if v == k]
dis_k
# [2, 3]

if dis_k == []:
    print(-1)
else:
    while dis_k:
        print(dis_k.pop(0))
# 2
# 3

연습으로 미로 탐색 백준 2178번 문제를 풀어보자.

from collections import deque

디큐는 속도가 빠른 리스트로 생각해도 좋다.

코딩 테스트에서 파이썬으로 Queue, BFS, FIFO 방식의 알고리즘 접근이 필요할 때 리스트를 디큐로 바꾸어주면 속도 이슈 해결이 가능하다.

a_list = [1, 2, 3, 4, 5]
# [1, 2, 3, 4, 5]

a_dq = deque(a_list)
# deque([1, 2, 3, 4, 5])

이렇게 간단하게 디큐 함수로 바꾸어주기만 하면 된다.

a_dq.pop()
a_dq.popright()
# 5

a_dq.popleft()
# 1

a_dq
# deque([2, 3, 4])

a_dq.append(1004)
# deque([2, 3, 4, 1004])

• 디큐 맨 마지막 값을 뺄 때 : .pop()
• 디큐 맨 처음 값을 뺄 때 : .popleft()
  • 주의 / .pop(0)과 같이 사용하면 에러 발생!
• pop과 popleft 모두 기존의 디큐를 수정, 업데이트하는 파괴적 함수!
• 디큐 맨 뒤에 값을 추가할 때 : .append()

디큐를 활용한 bfs

graph_list = [
    [],
    [2,3,8], 
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]


def bfs(graph, start):
    need_visit = deque([])
    visited    = deque([])
    need_visit.append( start )
    while need_visit:
        node = need_visit.popleft()
        if node not in visited:
            visited.append(node)
            temp = graph[node]
            temp_reverse = list(reversed(temp))
            need_visit.extend( temp_reverse )
    return visited
    
    
  bfs(graph_list, 1)
  # deque([1, 8, 3, 2, 7, 5, 4, 6])