1707 이분 그래프

• 문제
  • 1707번: 이분 그래프
• 해설

  • import sys
    
    sys.setrecursionlimit(99999)
    
    test_case_count = int(sys.stdin.readline().strip()[0])
    input_gen = (list(map(int, x.strip().split())) for x in sys.stdin.readlines())
    
    
    def trans(x):
        return -x
    
    
    def dfs(vertex, adj, chk, label_history, prev, res):
        chk[vertex] = True
    
        # labeling 한 적 없었으면 labeling
        if vertex not in label_history:
            label_history[vertex] = trans(prev)
    
        for neighbor in adj[vertex]:
            # Not bipartite인 경우 dfs 종료
            if neighbor in label_history and label_history[neighbor] == label_history[vertex]:
                res.append(1)
                break
            if not chk[neighbor]:
                dfs(neighbor, adj, chk, label_history, label_history[vertex], res)
    
    
    def check_bipartite(adj, chk):
        res = []
        first = True
        for vertex in adj:
            if first:
                dfs(vertex, adj, chk, {}, 1, res)
                first = False
            if chk[vertex] == False:
                dfs(vertex, adj, chk, {}, 1, res)
        if res:
            print('NO')
        else:
            print('YES')
    
    
    for case in range(test_case_count):
        vertex_count, edge_count = next(input_gen)
        chk = [False] * (vertex_count + 1)
        adj = {}
        for y in range(edge_count):
            vertex_1, vertex_2 = next(input_gen)
            if vertex_1 not in adj:
                adj[vertex_1] = [vertex_2]
            else:
                adj[vertex_1].append(vertex_2)
            if vertex_2 not in adj:
                adj[vertex_2] = [vertex_1]
            else:
                adj[vertex_2].append(vertex_1)
        check_bipartite(adj, chk)

• 포인트
  • DFS 설정

1260 DFS와BFS

• 문제
  • 1260번: DFS와 BFS (acmicpc.net)
• 해설

  • import sys
    import queue
    
    sys.setrecursionlimit(99999)
    
    vertex_count, edge_count, start_vertex = [int(x) for x in sys.stdin.readline().strip().split()]
    edges = [list(map(int, x.strip().split())) for x in sys.stdin.readlines()]
    
    adj_dict = dict()
    chk_dict = dict()
    
    for edge in edges:
        vertex_1, vertex_2 = edge
        if vertex_1 not in adj_dict:
            adj_dict[vertex_1] = [vertex_2]
        else:
            adj_dict[vertex_1].append(vertex_2)
        if vertex_2 not in adj_dict:
            adj_dict[vertex_2] = [vertex_1]
        else:
            adj_dict[vertex_2].append(vertex_1)
    
    for vertex in adj_dict:
        chk_dict[vertex] = False
        adj_dict[vertex] = sorted(list(set(adj_dict[vertex])))
    
    sorted_vertex = sorted(list(chk_dict.keys()))
    chk_dict_bfs = chk_dict.copy()
    dfs_ans = []
    bfs_ans = []
    queue_for_bfs = queue.Queue()
    
    
    def dfs(vertex):
        chk_dict[vertex] = True
        dfs_ans.append(vertex)
        for k in adj_dict[vertex]:
            if not chk_dict[k]:
                dfs(k)
    
    
    def bfs(vertex):
        chk_dict_bfs[vertex] = True
        bfs_ans.append(vertex)
        for k in adj_dict[vertex]:
            if not chk_dict_bfs[k]:
                chk_dict_bfs[k] = True
                queue_for_bfs.put(k)
        if queue_for_bfs.qsize():
            bfs(queue_for_bfs.get())
    
    
    if start_vertex in adj_dict.keys():
        dfs(start_vertex)
        bfs(start_vertex)
        print(' '.join([str(x) for x in dfs_ans]))
        print(' '.join([str(x) for x in bfs_ans]))
    else:
        print(start_vertex)
        print(start_vertex)

• 포인트
  • BFS와 DFS를 구현

문제:www.acmicpc.net/problem/1707

비고:

-dfs로 돌면서 label(dictionary)를 잡고 돌고

-이웃node가 label이 없으면 이전 nodes' label과 반대로 달고

-새로운 node마다 labeled 이웃 전체(이전 node를 지우고하는게 아니라)에 대해 label이 같은지 테스트가 관건

-난이도 중

내소스코드:

boj.kr/79b09fa7f4294aa19104a5d58d317c05