dfs, bfs 탬플릿 코드

DFS (좌표 형태 순회용)

def dfs(x, y):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if isRectangle(nx, ny) and copyed_maps[nx][ny] == 1 and chk[nx][ny] == -1:
            chk[nx][ny] = 1
            dfs(nx, ny)

def isRectangle(x, y):
    if 0 <= x < n and 0 <= y < n:
        return True
    return False

# 예시 그래프 (지도)와 chk 배열 초기화
n = 5
copyed_maps = [
    [1, 1, 0, 0, 0],
    [0, 1, 0, 1, 1],
    [0, 1, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 1]
]
chk = [[-1 for _ in range(n)] for _ in range(n)]

# 시작점 방문 표시 및 DFS 호출
chk[0][0] = 1
dfs(0, 0)

# chk 배열 출력
for row in chk:
    print(row)

 

DFS ( 노드와 노드 순회용)

n = int(input())
connects = int(input())

connectList = [[0] * (n + 1) for _ in range(n + 1)]
visited = [0 for _ in range(n + 1)]
answer = 0
for _ in range(connects):
    a, b = map(int, input().split())

    connectList[a][b] = 1
    connectList[b][a] = 1


def dfs(num):
    global answer
    visited[num] = 1
    answer += 1
    for i in range(n + 1):
        if visited[i] == 0 and connectList[num][i] == 1:
            dfs(i)


dfs(1)
print(answer - 1)

 

BFS

def bfs(x, y):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    q = deque([])
    q.append([x, y])

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if isRetangle(nx, ny) and copyed_maps[nx][ny] == 1 and chk[nx][ny] == -1:
                chk[nx][ny] = 1
                q.append([nx, ny])

def isRetangle(x, y):
    if 0 <= x < n and 0 <= y < n:
        return True
    return False

 

 

맵, 체크 함수 초기화 코드

copyed_maps = [[0 for _ in range(n)] for _ in range(n)]
chk = [[-1 for _ in range(n)] for _ in range(n)]

 

DFS, BFS 그래프 탐색 풀 때, 이렇게 탬플릿 코드를 기억 해두면 풀기 좋으므로, 기억용 포스팅!