[2024.02.16] Queue

BFS(Breadth First Search)

: 너비우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식

인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용함

• BFS 알고리즘

def BFS(G, v): #그래프 G, 탐색 시작점 v
    visited = [0] * (n+1) #n: 정점의 개수
    queue = [] #큐 생성
    queue.append(v) #시작점 v를 큐에 삽입
    while queue: #큐가 비어있지 않은 경우
        t = queue.pop(0) #큐의 첫번째 원소 반환
        if not visited[t]: #방문되지 않은 곳이라면
            visited[t] = True #방문한 것으로 표시
            visit(t) #정점 t에서 할 일
            for i in G[t]: #t와 연결된 모든 정점에 대해
                if not visited[i]: #방문되지 않은 곳이라면
                    queue.append(i) #큐에 넣기

• 연습문제3 (BFS 알고리즘)

'''
V E: 1~V번까지 V개의 정점. E개의 간선
E개의 간선 정보
7 8
1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7
'''
def bfs(s, N): #시작정점 s, 노드 개수 N
    q = [] #큐
    visited = [0] * (N+1) #visited
    q.append(s) #시작점 enqueue
    visited[s] = 1 #시작점 방문표시
    while q: #큐가 비워질 때까지... (남은 정점이 있으면)
        t = q.pop(0)
        # t에서 할 일
        print(t)
        for i in adjl[t]: #t에 인접인 정점 i
            if  visited[i] == 0: #방문하지 않은 정점이라면,
                q.append(i) #enqueue
                visited[i] = 1 + visited[t] #방문 표시

V, E = map(int, input().split())
arr = list(map(int, input().split()))

#인접리스트
adjl = [[] for _ in range(V+1)]
for i in range(E):
    n1, n2 = arr[i*2], arr[i*2+1]
    adjl[n1].append(n2)
    adjl[n2].append(n1) #무방향 그래프

bfs(1, V)

• 노드의 거리 (SWEA)

def bfs(s, N, G): #시작정점 s, 노드 개수 N
    q = [] #큐 생성
    visited = [0] * (N+1) #visited 생성
    q.append(s) #시작점 enqueue
    visited[s] = 1 #enqueue 표시
    while q: #처리 안 된 정점이 남아있으면,
        t = q.pop(0) #처리할 정점 dequeueㄴ
        if t == G:
            return visited[t] - 1 #최단 경로 간선 수
        for i in adjl[t]: #t의 인접 정점이
            if visited[i] == 0: #enqueue 되지 않았으면(처리된 적이 없으면),
                q.append(i)
                visited[i] = visited[t] + 1
    return 0 #G까지 경로가 없는 경우

T = int(input())
for tc in range(1, T+1):
    V, E = map(int, input().split())

    #인접리스트
    adjl = [[] for _ in range(V+1)]
    for i in range(E):
        n1, n2 = map(int, input().split())
        adjl[n1].append(n2)
        adjl[n2].append(n1) #무방향 그래프
    S, G = map(int, input().split())

    print(f'#{tc}', bfs(S, V, G))

• DFS & BFS (강사님 코드)

V = 7
arr = [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7]
#     u1, v1, u2, v2, ...

# 그래프를 표현 : 인접 리스트(노드 간의 연결 정보)
# 인접 리스트 초기화
adjl = [[] for _ in range(V+1)]
for idx in range(0, len(arr), 2):
    u, v = arr[idx], arr[idx+1]
    adjl[u].append(v) # u -> v
    adjl[v].append(u) # v -> u

# BFS -> 해당 노드를 인접된 노드를 차례대로 방문
def bfs(start):
    visited = [False] * (V+1)
    queue = [] # 큐 : 방문할 노드들
    # 시작 정점 start에 대해서 방문 체크와 큐에 삽입
    visited[start] = True
    queue.append(start)
    while queue: # 큐가 빌 때까지 반복
        u = queue.pop(0)
        print('-', u, end='')
        # 인접되어 있는 방문하지 않은 노드들을 큐에 삽입
        for v in adjl[u]: # u -> v1, v2, ...
            if visited[v] == False:
                queue.append(v)
                visited[v] = True

bfs(1) # 1번 노드를 기준으로 해서 BFS 탐색 진행

print()

# DFS -> 해당 노드에서 다른 노드로 먼저 깊게 탐색
# 스택 : 다시 되돌아갈 수 있는 노드들
def dfs(start):
    # 기저조건(종료조건): 이미 방문한 노드라면 종료 => 의미 없음
    # if visited[start]:
    #     return
    visited[start] = True
    print('-', start, end='')
    # 재귀호출: 다음 노드를 계속 탐색
    for v in adjl[start]: # start -> v1, v2, ...
        if visited[v] == False:
            dfs(v)

visited = [False] * (V+1)
dfs(1)

DFS vs BFS

• DFS: 깊이 우선 탐색, 노드에서 가능한 한 깊게 탐색을 먼저 진행 (단, 더 이상 탐색을 진행할 수 없는 상황일 때, 이전 노드로 되돌아와서 다시 탐색을 수행)
  -자료구조: 스택
  -쓰임: 되돌아갈 수 있는 노드들

• BFS: 너비 우선 탐색, 노드에서 인접한 노드를 순차적으로 탐색하는 방법
  -자료구조: 큐
  -쓰임: 방문할 노드들

장단점

• DFS 장점
  구현이 상당히 간단함 (재귀적인 코드로 짜는 경우 코드가 간결해짐)
  스택이라는 자료구조를 사용하기 때문에 메모리 사용량이 적음.

• DFS 단점
  최단 경로가 아닌, 다른 경로를 결과값으로 찾을 수 있음 (최적해가 아닐 수 있음)

• BFS 장점
  최단 경로를 보장함 (최소 이동 횟수를 알 수 있음)

• BFS 단점
  구현이 다소 복잡함
  DFS에 비해 메모리 사용량이 많음

* 결론 -> 문제에 따라서 DFS, BFS 적절하게 활용해야 함!
BFS 탐색 => 최단 경로, 최소 시간
DFS 탐색 => 탐색할 노드 多, 경로 자체가 중요하지 않은 경우

SWEA 암호생성기 (강사님 코드)

T = 10
for _ in range(1, T+1):
    tc = int(input())
    password = list(map(int, input().split()))

    #로직
    i = 1 #감소시킬 값 (카운트 값)
    while password[-1] != 0: #패스워드의 맨 뒤 요소가 0이 될 때까지 반복
        # 패스워드를 앞에서 하나의 값을 꺼내어 i씩 감소시키고
        x = password.pop(0)
        x -= i
        # x가 0 이하가 된다면 0으로 만들어준다
        if x < 0:
            x = 0
        # 다시 뒤에 삽입 (그리고 i는 1 증가)
        password.append(x)
        i += 1
        if i > 5:
            i = 1

    print(f'#{tc}', *password)

SWEA 재미있는 오셀로 게임 (강사님 코드)

# 재미있는 오셀로 게임 ^__^
dx = [-1, 1, 0, 0, -1, 1, 1, -1]
dy = [0, 0, -1, 1, -1, -1, 1, 1]

# (x, y) 좌표로부터 i 방향으로 상대 돌이 사이에 껴 있다면
# 이 돌들을 나의 돌로 바꾸기
def check(boards, N, x, y, color, dir):
    stack = []
    # 편의를 위해 한 칸만 이동 (상대 돌들을 확인)
    x = x + dx[dir]
    y = y + dy[dir]

    while True:
        # 보드판을 벗어난 경우 & 빈 영역을 만난 경우
        if 0 > x or x >= N or 0 > y or y >= N or boards[x][y] == 0:
            return
        # 나의 돌이 있는 경우
        elif boards[x][y] == color:
            break
        # 상대의 돌이 있는 경우
        elif boards[x][y] != color:
            stack.append((x, y))
            x = x + dx[dir]
            y = y + dy[dir]

    # 내가 공격할 수 있는 상황이라면 (돌을 가져갈 수 있는 상황)
    # 스택 안의 모든 돌을 나의 돌로 변경
    for x, y in stack:
        boards[x][y] = color

def solution(N, M, choices):
    # N*N 크기의 보드판
    boards = [[0] * N for _ in range(N)]
    mid = N // 2
    # 1을 흑돌, 2를 백돌
    boards[mid-1][mid-1] = 2
    boards[mid][mid] = 2
    boards[mid-1][mid] = 1
    boards[mid][mid-1] = 1

    # 좌표(x,y)에 대해서 color 돌을 놓는다
    for x, y, color in choices:
        boards[x-1][y-1] = color
        # 8방 탐색 (상대 돌을 가져온다)
        for i in range(8):
            check(boards, N, x-1, y-1, color, i)

    # 백돌과 흑돌의 수를 카운트
    w_cnt = 0
    b_cnt = 0
    for i in range(N):
        for j in range(N):
            if boards[i][j] == 1:
                b_cnt += 1
            elif boards[i][j] == 2:
                w_cnt += 1

    return b_cnt, w_cnt

T = int(input())
for tc in range(1, T+1):
    # 보드 한 변의 길이 N ,돌을 놓는 횟수 M
    N, M = map(int, input().split())
    choices = [list(map(int, input().split())) for _ in range(M)]

    b, w = solution(N, M, choices)
    print(f'#{tc} {b} {w}')

SWEA 미로2 (강사님 코드)

import sys
sys.stdin = open('input.txt', 'r')

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

def solution(maze):
    # 시작지점(2), 도착지점(3)
    def get_start_point():
        for i in range(100):
            for j in range(100):
                if maze[i][j] == 2:
                    return i, j

    sx, sy = get_start_point()

    # BFS 탐색 방법으로 시작점에서부터 도착지점으로 도달할 수 있는지 확인
    def bfs(sx, sy):
        # 미로에다가 내가 방문한 지점을 벽(1)으로 만들기
        # 시작점에 대한 방문 표기
        q = []
        maze[sx][sy] = 1 # 방문체크
        q.append((sx, sy))

        # 큐가 빌 때까지 (더 이상 방문할 수 있는 노드가 없을 때까지)
        while q:
            # 큐에서 좌표값을 하나 꺼내오고
            x, y = q.pop(0)
            # 해당 좌표에서 상하좌우 탐색
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                # 좌표가 바깥을 벗어난 경우나 벽을 만난 경우는 다른 방향으로 탐색 진행
                if 0 > x or 0 > y or 100 <= x or 100 <= y or maze[nx][ny] == 1:
                    continue
                # (nx, ny) 방문을 해줘야 하므로
                # (nx, ny) 좌표가 도착 지점(3)일 때
                if maze[nx][ny] == 3:
                    return True

                maze[nx][ny] = 1
                q.append((nx, ny))

        return False


    # 도착 지점에 도달한 경우를 참/거짓으로 반환
    return bfs(sx, sy)

T = 10
for _ in range(1, T+1):
    tc = int(input())
    maze = [list(map(int, input())) for _ in range(100)] # 100*100 미로
    result = solution(maze)

    if result:
        ans = 1
    else:
        ans = 0

    print(f'#{tc}', ans)