✏️ 1697번

문제

💡 문제 아이디어

• bfs 를 이용하여 풀기
• 다른 블로그들 참고해보니 bfs 풀 때 deque 를 많이 이용하는 것같아서 참고해보았다
  from collections import deque

👀 풀이

# 1697

import sys
from collections import deque

n,k = map(int, sys.stdin.readline().split())

dist = [0] * (10**5 +1) 
# dist 의 인덱스는 거리들 (ex : 처음에 n이 5면 인덱스가 5인 부분이 1)
# 해당 인덱스의 값은 시간 초 

def bfs() :
    q = deque()
    q.append(n)

    while q : # queue 가 없을 때까지 반복
        x = q.popleft()
        if x == k :
            print(dist[x])
            return
        for i in (x-1, x+1, 2*x) : # n이 5일 경우 (4,6,10)
            if 0 <= i <= 10**5 and not dist[i] :
                dist[i] = dist[x] + 1 # 그로부터 1초가 지났으니까
                q.append(i)



bfs()
    

✏️ 1707번

문제

💡 문제 아이디어

처음에 '이분 그래프' 에 대한 개념을 정확히 이해하지 못했다.

이분 그래프

• 개념 자체는 '정점을 2그룹으로 나눌 수 있으되 같은 그룹의 정점끼리는 간선으로 이어지지 않은 경우'를 뜻한다
  
• 집합을 두 가지로 나뉠 때, 같은 집합 노드 끼리는 서로 인접하지 않아야 한다
• 즉, 코드를 짤 때 인접한 노드끼리는 서로 다른 색이어야 하도록 짜야한다

👀 풀이

# 1707

import sys
from collections import deque

K = int(sys.stdin.readline())

results = []

def bfs(start) :
    q = deque()
    q.append(start)
    colors[start] = 1
    while q :
        qh = q.popleft()
        for i in graph[qh] :
            if colors[i]==0 :
                q.append(i)
                colors[i] = -1 * colors[qh]
            elif colors[i]==colors[qh]:
                return False 
    return True
    

for _ in range(K) :
    V , E = map(int, sys.stdin.readline().split())
    bg = 'YES'
    graph = [[] for _ in range(V+1)]
    colors = [0 for _ in range(V+1)]
    visited = [False for _ in range(V+1)]
    for _ in range(E) :
        a,b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    for i in range(1,V+1) :
        if colors[i] == 0 : # 아직 색을 칠하지 않은 노드일 경우
            if not bfs(i) :
                bg = 'NO'
                break
    results.append(bg)

for r in results  :
    print(r)