[내일배움캠프 5-1일] 스쿼드 문제, dfs, bfs, 섬 개수 세기

dfs 와 bfs

N, M, V = map(int, input().split())

# 그래프 초기화
graph = [[] for _ in range(N+1)]

# graph 구성하기, 노드 두개가 연결되었다면 양쪽에 서로를 인자로 넣어주는 것
# 정렬까지
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()

문제에서 나온 N, M, V를 입력받고 그래프를 먼저 구성한다.

0번 인덱스는 사용하지 않고 1번부터 N번까지 사용하므로 범위를 N+1까지 설정.

이후 반목문을 통해 a, b를 받고 이들은 서로 연결된 노드이므로 각각의 인덱스에 서로를 넣어준다. 이후 정렬.

 

# 재귀적으로 dfs를 수행
def dfs(start):
    dfs_result.append(start)
    # 현재 노드(start)의 모든 인접 노드를 탐색
    for neighbor in graph[start]:
        # 인접 노드가 dfs_result에 없다면 재귀적으로 다시 dfs 수행
        if neighbor not in dfs_result:
            dfs(neighbor)

dfs_result = []

dfs함수를 생성.

강의에서 배운 재귀적인 방법을 선택했다.

함수 외부에 dfs_result를 만들어 결과를 저장.

 

from collections import deque

# deque를 사용해서 bfs 수행
def bfs(start):
    # queue 생성 후 start 추가
    queue = deque([start])
    visited[start] = True

    # queue가 빌 때까지 수행
    while queue:
        # queue의 첫번째 인자 pop 후 bfs_result에 추가
        node = queue.popleft()
        bfs_result.append(node)
        # node의 인접 노드 탐색
        for neighbor in graph[node]:
            # 인접 노드 visited가 False라면 queue에 추가, visited 를 True로 변환
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

# visited는 방문 여부를 위한 리스트(bfs에서 사용)
visited = [False] * (N+1)

bfs_result = []

visited라는 리스트를 만들어 인덱스에 False를 할당하고.

함수 내부에 queue를 만들어 하나씩 pop, 이를 bfs_result에 추가한다.

pop한 인자(node)의 모든 인접 노드를 돌면서 visited가 False인지 확인하고 False라면 True로 변환 후 queue에 추가.

queue가 빌 때까지 반복한다.

 

from collections import deque

# 재귀적으로 dfs를 수행
def dfs(start):
    dfs_result.append(start)
    # 현재 노드(start)의 모든 인접 노드를 탐색
    for neighbor in graph[start]:
        # 인접 노드가 dfs_result에 없다면 재귀적으로 다시 dfs 수행
        if neighbor not in dfs_result:
            dfs(neighbor)

# deque를 사용해서 bfs 수행
def bfs(start):
    # queue 생성 후 start 추가
    queue = deque([start])
    visited[start] = True
    
    # queue가 빌 때까지 수행
    while queue:
        # queue의 첫번째 인자 pop 후 bfs_result에 추가
        node = queue.popleft()
        bfs_result.append(node)
        # node의 인접 노드 탐색
        for neighbor in graph[node]:
            # 인접 노드 visited가 False라면 queue에 추가, visited 를 True로 변환
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

N, M, V = map(int, input().split())

# 그래프 초기화
graph = [[] for _ in range(N+1)]

# visited는 방문 여부를 위한 리스트(bfs에서 사용)
visited = [False] * (N+1)

dfs_result = []
bfs_result = []

# graph 구성하기, 노드 두개가 연결되었다면 양쪽에 서로를 인자로 넣어주는 것
# 정렬까지
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()

dfs(V)
bfs(V)
print(' '.join(map(str, dfs_result)))
print(' '.join(map(str, bfs_result)))

전체 코드

---

유기농 배추

딱 문제를 보자마자 섬 개수 세기 문제가 떠올랐다.

아예 같은 문제였고 grid만 입력값을 통해 만들면 되는 문제였음.

T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())

    # 0으로 채워진 grid를 우선 생성
    grid = [[0 for _ in range(N)] for _ in range(M)]

    # 주어진 좌표를 1로 변경
    for _ in range(K):
        X, Y = map(int, input().split())
        grid[X][Y] = 1

    print(count_worms(grid))

입력값은 이런 식으로 받음.

우선 N, M으로 grid의 틀을 구성한다. 모두 0으로 값을 할당.

K만큼 반복하여 X, Y를 받게 되는데 이 좌표만 grid에서 1로 변환하면 됨.

grid 생성 완료

 

def count_worms(grid):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    rows, cols = len(grid), len(grid[0])
    cnt = 0

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] != 1:
                continue

            cnt += 1
            stack = [(row, col)]

            while stack:
                x, y = stack.pop()
                grid[x][y] = 0
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != 1:
                        continue
                    stack.append((nx, ny))
    return cnt

섬 세기 문제와 정확히 같은 함수. 함수명만 바꿔줬다.

사실 이 부분 다 까먹어서 다시 수업을 들어야 할 듯.

def count_worms(grid):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    rows, cols = len(grid), len(grid[0])
    cnt = 0

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] != 1:
                continue

            cnt += 1
            stack = [(row, col)]

            while stack:
                x, y = stack.pop()
                grid[x][y] = 0
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != 1:
                        continue
                    stack.append((nx, ny))
    return cnt


T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())

    # 0으로 채워진 grid를 우선 생성
    grid = [[0 for _ in range(N)] for _ in range(M)]

    # 주어진 좌표를 1로 변경
    for _ in range(K):
        X, Y = map(int, input().split())
        grid[X][Y] = 1

    print(count_worms(grid))

전체 코드

---

오늘의 회고

강의 진도도 나가고 숙제도 하느라 은근 시간이 없었다. 중간에 재귀 특강도 있어서 더 그랬던 것 같다.

그래도 나름 집중해서 잘 했음. 유기농 배추문제 함수 다시 강의 찾아서 듣자.

 

내일 목표는 3주차 진도 마저 나가기 + 스쿼드 숙제 두개 완료하기