[DFS/BFS] 1707번, 4963번 복습

1. 이분그래프 -BFS로 풀기

DFS풀이 - 이분그래프

from collections import deque
import sys
input = sys.stdin.readline

k = int(input())

def bfs(v,color):
    queue = deque()
    queue.append(v)
    colors[v]=color #방문표시
    
    while queue:
        pop = queue.popleft()
        for i in graph[pop]:
            if colors[i]==0:
                queue.append(i)
                colors[i] = -colors[pop]
            elif colors[pop]==colors[i]:
                return False
        
    return True



for i in range(k):
    v,e = map(int,input().split())
    graph = [[] for i in range(v+1)]
    colors = [0]*(v+1)
    
    for j in range(e):
        v1,v2 = map(int,input().split())
        graph[v1].append(v2)
        graph[v2].append(v1)
    
    isBG=True
    for k in range(1,v+1):
        if colors[k]==0:
            if bfs(k,1) is False:
                isBG =False
                break
    
    print("YES" if isBG else "NO")

2. 섬의 개수

DFS 풀이 - 섬의 개수

from collections import deque
import sys

input = sys.stdin.readline

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

def bfs(x,y):
    queue = deque()
    queue.append([x,y])
    visited[x][y]=True
    
    while queue:
        px,py = queue.popleft()
        for i in range(len(dx)):
            nx = px+dx[i]
            ny = py+dy[i]
            if nx<0 or nx>=h or ny<0 or ny>=w:
                continue
            elif graph[nx][ny]==1 and visited[nx][ny]==False:
                queue.append([nx,ny])
                visited[nx][ny]=True
            


while True:
    w, h = map(int,input().split()) #너비 높이
    graph=[]
    
    if w==0 and h==0: # 0 0을 받으면 종료
        break
    visited = [[False]*w for i in range(h)]
    
    for i in range(h):
        line = list(map(int, input().split()))
        graph.append(line)
        
    answer = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j]==1 and visited[i][j]==False:
                bfs(i,j)
                answer+=1
    
    print(answer)

둘 다 dfs->bfs 함수로 바뀐 것 빼고는 바뀐 점은 없다.