[SWEA] 5521. 상원이의 생일파티

문제

풀이 (DFS)

• s : 출발위치, c : 현재까지의 거리
• 상원이를 1이라고 따졌을 때 친구의 친구까지이기때문에 c는 1 - 2(친구) -> 3(친구의 친구) 3까지만 따져보면 된다. c=3 일때는 거기서 더 따져보는게 의미가 없기 때문에 continue로 while문을 다시 돌린다. break를 하면 그 다음에 있는 stack에 c가 3이하인 경우가 있기 때문에 안됨

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    arr = [[] for _ in range(N+1)]
    visit = [0] * (N+1)
    cnt = 0
 
    for _ in range(M):
        a, b = map(int, input().split())
        arr[a].append(b)
        arr[b].append(a)

    stack = [(1, 1)]
    visit[1] = 1
    while stack:
        s, c = stack.pop()
        if c >= 3:
            continue
        for i in arr[s]:
            if visit[i] == 0:
                visit[i] = c+1
                cnt += 1
            elif visit[i] > c+1:
                visit[i] = c+1
            stack.append((i, c+1))            

    print(f'#{tc}', cnt)

• 테스트 케이스에는 없지만 그림과 같은 상황에서는 DFS 로 따졌을 때 1 -> 3 -> 4 -> 5를 먼저 가보게 되고(스택이기 때문에 뒤에 있는 게 먼저 꺼내짐) visit[5] = 4가 저장된다. 하지만 그 다음에 1 -> 2 -> 5를 따지면 visit[5] = 3으로 갱신해야 한다. visit은 단순히 현재 경로까지의 거리가 얼마나 되는지를 따지기 위함이고 c가 3이하일때는 visit[i] == 0일때 이미 카운팅을 했기 때문에 굳이 그 조건문에서는 카운팅을 한 번 더 해줄 필요가 없다.
  

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    arr = [[] for _ in range(N+1)]
    visit = [0] * (N+1)
    cnt = 0
  
    for _ in range(M):
        a, b = map(int, input().split())
        arr[a].append(b)
        arr[b].append(a)
 
    stack = [(1, 1)]
    visit[1] = 1
    while stack:
        s, c = stack.pop()
        if c >= 3:
            continue
        for i in arr[s]:
            if visit[i] == 0:
                visit[i] = c+1
                cnt += 1
            elif visit[i] <= c+1:
                continue
            elif visit[i] > c+1:
                visit[i] = c+1
            stack.append((i, c+1))
        print('visit', visit)       
 
    print(f'#{tc}', cnt)
"""
1
6 5
1 2
1 3
3 4
4 5
2 5
visit [0, 1, 2, 2, 0, 0, 0]
visit [0, 1, 2, 2, 3, 0, 0]
visit [0, 1, 2, 2, 3, 4, 0]
visit [0, 1, 2, 2, 3, 4, 0]
visit [0, 1, 2, 2, 3, 3, 0]
visit [0, 1, 2, 2, 3, 3, 0]
"""

풀이 (BFS)

• 이 문제는 BFS로 풀면 쉽다. 친구의 친구까지 구하고 나면 그 다음은 친구의 친구의 친구를 구하게 되기 때문에 더 이상 구할 필요가 없어서 바로 break 로 반복문을 끝내면 된다.

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    friends = [[] for _ in range(N+1)]
    visit = [0] * (N+1)
    cnt = 0

    for _ in range(M):
        a, b = map(int, input().split())
        friends[a].append(b)
        friends[b].append(a)

    queue = [(1, 0)]
    while queue:
        s, c = queue.pop(0)
        visit[s] = 1
        if c >= 2:
            break
        for i in friends[s]:
            if visit[i] == 0:
                visit[i] = 1
                cnt += 1
                queue.append((i, c+1))

    print(f'#{tc}', cnt)

• DFS로 풀 때 가장 가까운 거리로 계속 갱신해줘야 더 구해나갈 수 있다. 테스트 케이스에서는 그 부분을 고려하지 않고 짜도 답이 나오지만 실제로 계산해보면 그렇다...