[TIL_Carrotww] 118 - 23/06/03

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 백준 스타트 링크

처음에 dp로 접근하였는데 풀다보니 bfs인 것 같아서 bfs로 풀이하였다.

• 내 풀이

def solve():
    import sys
    from collections import deque
    total, start, end, up, down = map(int, sys.stdin.readline().split())
    dp = [float('inf')] * (total + 1)
    dp[start] = 0
    queue = deque()
    queue.append([start, 0])

    while queue:
        cur_node, cnt = queue.popleft()
        if cur_node == end:
            print(cnt)
            return
        up_node = cur_node + up
        if 1 <= up_node <= total and dp[up_node] > cnt+1:
            dp[up_node] = cnt+1
            queue.append([up_node, cnt+1])
        down_node = cur_node - down
        if 1 <= down_node <= total and dp[down_node] > cnt+1:
            dp[down_node] = cnt+1
            queue.append([down_node, cnt+1])
    print('use the stairs')

if __name__ == "__main__":
    solve()

🔍 백준 거짓말

bfs라고 느낌이 왔는데 문제에서 graph가 제대로 주어지지 않아 내가 만들어야 한다.
코드가 좀 복잡한데
1. 파티 번호에 따라 참가한 사람들 dictionary
2. 어떤 사람이 참가한 파티의 파티 넘버 dictionary
두 가지를 만들어서 bfs로 거짓말을 판별하는 사람들이 속해있는 파티, 해당 파티에 참가하는 사람들, 또 그 사람들이 참가하는 파티를 bfs로 모두 찾아주어서 결과값에서 빼주었다.

• 내 코드

def solve():
    import sys
    from collections import defaultdict, deque
    N, M = map(int, sys.stdin.readline().split())
    know_people = list(map(int, sys.stdin.readline().split()))
    if know_people[0] == 0:
        print(M)
        return
    else:
        know_people = know_people[1::]
    graph = defaultdict(list)
    party = dict()

    for party_num in range(1, M+1):
        cur_party = list(map(int, sys.stdin.readline().split()))
        party_people_list = cur_party[1::]
        party[party_num] = party_people_list
        for people in party_people_list:
            graph[people].append(party_num)

    visited = [False for _ in range(N+1)]
    queue = deque()
    for people in know_people:
        queue.append(people)

    while queue:
        cur_people = queue.popleft()
        for party_num in graph[cur_people]:
            for people in party[party_num]:
                if visited[people]:
                    continue
                visited[people] = True
                queue.append(people)

    result = M
    for people_list in party.values():
        is_true = False
        for people in people_list:
            if visited[people]:
                is_true = True
                break
        if is_true:
            result -= 1

    print(result)

if __name__ == "__main__":
    solve()