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 설정

• 문제
  • 1697번: 숨바꼭질
• 해설

  • import sys
    from collections import deque
    
    sys.setrecursionlimit(1000000)
    
    subin, sister = [*map(int, sys.stdin.readline().strip().split())]
    
    # 시작부터 수빈이가 선두인 경우는 수빈이가 뒷걸음치는 것만 가능
    if subin >= sister:
        print(subin - sister)
        sys.exit()
    
    q = deque()
    map_ = [0] * 200000
    
    
    def bfs(subin_position, current_seconds):
        candidates = [subin_position - 1, subin_position + 1, 2 * subin_position]
        candidates = [candidate for candidate in candidates
                      if 0 <= candidate <= 100000 and map_[candidate] == 0]
        next_seconds = current_seconds + 1
        for candidate in candidates:
            # 수빈이가 동생 찾았을 때
            if candidate == sister:
                print(next_seconds)
                sys.exit()
    
            map_[candidate] = next_seconds
    
            q.appendleft((candidate, next_seconds))
        if len(q):
            bfs(*q.pop())
    
    
    bfs(subin, 0)

• 포인트
  • BFS 문제인 걸 알기

• 문제
  • 1476번: 날짜 계산
• 해설

  • import sys
    
    earth, sun, moon = tuple([int(x) for x in sys.stdin.readline().split()])
    total = 15 * 28 * 19
    
    
    def mod(value, base):
        if value == 0:
            return base
        else:
            return value
    
    
    for i in range(1, total + 1, 1):
        if (earth, sun, moon) == (mod(i % 15, 15), mod(i % 28, 28), mod(i % 19, 19)):
            print(i)
            break

• 포인트
  • 중국인의 나머지 정리를 통해, 해가 15 * 28 * 19 내에 유일하다는 점을 파악
  • BruteForce
  • 해를 찾을 때 까지만 반복

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를 구현

• 문제
  • 1182번: 부분수열의 합
• 해설

  • import sys
    
    int_cnt, target_sum = [int(x) for x in sys.stdin.readline().split()]
    
    given_seq = [int(x) for x in sys.stdin.readline().split()]
    
    
    def go(seq, cur_sum, cur_ind, used_inds):
        res = 0
    
        # 정답
        if cur_sum == target_sum and cur_ind == len(seq) and used_inds:
            return 1
    
        # 불가능
        if cur_ind == len(seq):
            return 0
    
        if cur_ind < len(seq):
            # 현재 idx를 사용한 경우
            res += go(seq, cur_sum + seq[cur_ind], cur_ind + 1, used_inds + [cur_ind])
            # 현재 idx를 사용하지 않은 경우
            res += go(seq, cur_sum, cur_ind + 1, used_inds)
    
        return res
    
    
    print(go(given_seq, 0, 0, []))

• 포인트
  • BruteForce임을 눈치챈다.
  • 첫 원소가 포함될 때 안될 때, 각 경우마다 두번째 원소가 포함될 떄 안될 때, ... 재귀 구현

• 문제
  • 10971번: 외판원 순회 2
• 해설

  • import sys
    
    N = int(sys.stdin.readline())
    matrix = [list(map(int, x.strip().split())) for x in sys.stdin.readlines()]
    base_idx = [x for x in range(N)]
    
    
    def next_permutation(list):
        last_asc_idx = 0
        for i in range(len(list) - 1):
            if list[i] < list[i + 1]:
                last_asc_idx = i
    
        val_at_last_asc_idx = list[last_asc_idx]
        last_idx_larger_than_val_at_last_asc_idx = 0
        for j in range(last_asc_idx + 1, len(list), 1):
            if val_at_last_asc_idx < list[j]:
                last_idx_larger_than_val_at_last_asc_idx = j
    
        if last_asc_idx == 0 and last_idx_larger_than_val_at_last_asc_idx == 0:
            return False
        else:
            list[last_asc_idx], list[last_idx_larger_than_val_at_last_asc_idx] = \
                list[last_idx_larger_than_val_at_last_asc_idx], list[last_asc_idx]
            last_idx_larger_than_val_at_last_asc_idx = len(list) - 1
            while (last_asc_idx + 1 < last_idx_larger_than_val_at_last_asc_idx):
                list[last_asc_idx + 1], list[last_idx_larger_than_val_at_last_asc_idx] = \
                    list[last_idx_larger_than_val_at_last_asc_idx], list[last_asc_idx + 1]
                last_asc_idx += 1;
                last_idx_larger_than_val_at_last_asc_idx -= 1
            return True
    
    
    def factorial(k):
        if k == 0 or k == 1:
            return 1
        else:
            res = k
            for i in range(1, k, 1):
                res *= i
            return res
    
    
    total_available_count = factorial(N - 1)
    
    res = []
    for j in range(total_available_count):
        cost = 0
        out_inner_loop = False
    
        # 마지막 도시에서 처음 도시로 가지 못하는 경우 발견
        if matrix[base_idx[N - 1]][base_idx[0]] == 0:
            # 다음 이동 경로 체크
            next_permutation(base_idx)
            continue
        else:
            cost += matrix[base_idx[N - 1]][base_idx[0]]
    
        for i in range(N - 1):
            # 이동이 불가능한 도시의 경우
            if matrix[base_idx[i]][base_idx[i + 1]] == 0:
                out_inner_loop = True
                break
            else:
                cost += matrix[base_idx[i]][base_idx[i + 1]]
        if out_inner_loop:
            # 다음 이동 경로 체크
            next_permutation(base_idx)
            continue
    
        # 가능한 경우가 처음 나왔을 때
        if len(res) == 0:
            res.append(cost)
    
        # 가능한 경우를 이전과 비교  
        else:
            if cost < res[0]:
                res[0] = cost
    
        # 다음 이동 경로 체크
        next_permutation(base_idx)
    
    print(res[0])

• 포인트
  • BruteForce임을 알아채야한다.
  • next permutation을 구현할 수 있어야한다.