[python] SWEA - 1249. 보급로 / 5521. 상원이의 생일파티

1. 보급로

문제 해결

1. 다익스트라 알고리즘 + 힙큐

2. 가중치 리스트와 방문 리스트를 만들어 준다.

3. 힙큐를 이용해 가중치가 가장 낮은 점을 선택하고

4. 주변을 탐색하여 최소 가중치를 선택해 가중치를 점점 누적해 나아간다.

소스 코드

import heapq

for tc in range(1, 1+int(input())):
    n = int(input())
    maps = [list(map(int, list(input()))) for _ in range(n)]

    # dist: 가중치를 누적한 리스트, visit: 선택했는지 안했는지
    dist = [[float('inf')]*n for _ in range(n)]
    visit = [[False]*n for _ in range(n)]

    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    pq = []
    # 0, 0부터 시작
    heapq.heappush(pq, [0, 0, 0])
    dist[0][0] = 0
    while pq:
        w, x, y = heapq.heappop(pq)

        # 이미 선택했었다면 continue
        if visit[x][y]:
            continue

        # 선택하지 않았었다면 시작
        visit[x][y] = True

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < n:
                if not visit[nx][ny] and w < dist[nx][ny]:
                    dist[nx][ny] = maps[nx][ny] + w
                    heapq.heappush(pq, [dist[nx][ny], nx, ny])

    print('#{} {}'.format(tc, dist[-1][-1]))

 

 

출처: SW Expert Academy

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE

SW Expert Academy

 

2. 상원이의 생일파티

문제 해결

1. 방향 없는 단순 그래프 탐색

2. 인접리스트를 활용한다.

3. 재귀 함수로 DFS 탐색 (굳이🤔) (depth가 겨우 2이다. 단순 for문으로 가능)

소스 코드

def graph(depth, cur):
    # 친구의 친구까지 이므로 depth가 2이면 탐색을 멈춰준다.
    if depth == 2:
        return

    # cur의 친한 친구들은 neighbor을 찾고 friend리스트에 넣어준다.
    for neighbor in adj[cur]:
        friend.add(neighbor)
        # depth를 1증가시키고 친구의 친구를 찾아주기 위해 graph함수를 실행
        graph(depth+1, neighbor)


for tc in range(1, 1+int(input())):
    N, M = map(int, input().split())
    adj = {i: [] for i in range(1, N+1)}

    # 인접리스트 | 방향 없는 그래프
    for i in range(M):
        s, e = map(int, input().split())
        adj[s].append(e)
        adj[e].append(s)

    # 초대장을 보내줄 친구들을 담을 리스트 | 중복 X
    friend = set()
    friend.add(1)

    graph(0, 1)
    print('#{} {}'.format(tc, len(friend) - 1))

 

출처: SW Expert Academy

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWO3kT6F2oDFAV4&categoryId=AWWO3kT6F2oDFAV4&categoryType=CODE

SW Expert Academy