[SWEA] 2814. 최장 경로 D3

• BFS에 거리를 추가하는 방식으로 구현하였다.
• 테스트케이스 2개만 맞고 계속해서 오류가 떴다.
• 추가로 테스트케이스를 넣어봤는데 맞는 답이 나왔는데도 통과하지 못했다.
• 초기화도 했는데 무엇이 문제인지 머리가 터질 것 같다. ㅠㅠ
• 대부분의 사람들이 dfs로 문제를 풀어서 힌트를 얻지 못했다.

결론 : BFS 로 풀 수 없다.

BFS 1차수정 (오류)

• 일단 따로 table 필요 없이 visited 를 숫자배열로 배치
• global 로 maxV 변수를 쓰기 때문에 return 따로 해주지 않아도 된다.
• bfs 는 초기화시킬 필요 없을것 같고..
• bfs로 풀 수 있는건가?

import sys
sys.stdin = open('input.txt')

from collections import deque

def number_of_vertex_bfs(graph, start_node):
    global maxV

    visited[start_node] = 1
    queue.append(start_node)

    while queue:
        node = queue.popleft()
        for next_node in range(1, N+1):
            if not visited[next_node] and graph[node][next_node]:
                visited[next_node] = visited[node] + 1
                queue.append(next_node)

    if max(visited) > maxV:
        maxV = max(visited)


T = int(input())

for tc in range(1, T + 1):
    N, M = map(int, input().split()) # N개의 정점, M개의 간선

    graph = [[0] * (N + 1) for _ in range(N + 1)]

    for i in range(M):
        ni, nj = map(int, input().split())
        graph[ni][nj] = 1
        graph[nj][ni] = 1

    maxV = 0
    for start_node in range(1, N + 1):
        queue = deque()
        visited = [0] * (N + 1)
        number_of_vertex_bfs(graph, start_node)

    print("#{} {}".format(tc, maxV))

 

BFS 첫 답안(오류)

def number_of_vertex(graph, start_node):
    visited = [False] * (N + 1)
    queue = []
    table = [0] * (N + 1)

    queue.append(start_node)
    visited[start_node] = True
    table[start_node] = 1

    while queue:
        node = queue.pop(0)
        next_nodes = [x+1 for x in range(N)]
        for next_node in next_nodes:
            if graph[node][next_node] == 1 and visited[next_node] != True:
                queue.append(next_node)
                visited[next_node] = True
                table[next_node] = table[node] + 1

    return max(table)


T = int(input())

for tc in range(1, T + 1):
    N, M = map(int, input().split()) # N개의 정점, M개의 간선

    # 그래프 초기화
    graph = [[0] * (N + 1) for _ in range(N + 1)]

    for i in range(M):
        ni, nj = map(int, input().split())
        graph[ni][nj] = 1
        graph[nj][ni] = 1

    numbers_of_vertex = []
    for start_node in range(1, N + 1):
        numbers_of_vertex.append(number_of_vertex(graph, start_node))

    print("#{} {}".format(tc, max(numbers_of_vertex)))

 

DFS 로 참고해서 풀이(PASS)

재귀와 백트래킹을 위한 초기화가 관건

import sys
sys.stdin = open('input2.txt')


def number_of_vertex_dfs(graph, node, cnt):
    global maxV

    for next_node in range(1, N+1):
        if not visited[next_node] and graph[node][next_node]:
            visited[next_node] = 1
            number_of_vertex_dfs(graph, next_node, cnt+1)
            visited[next_node] = 0

    if cnt > maxV:
        maxV = cnt


T = int(input())

for tc in range(1, T + 1):
    N, M = map(int, input().split()) # N개의 정점, M개의 간선

    # 그래프 초기화
    graph = [[0] * (N + 1) for _ in range(N + 1)]

    for i in range(M):
        ni, nj = map(int, input().split())
        graph[ni][nj] = 1
        graph[nj][ni] = 1

    queue = []
    visited = [0] * (N + 1)

    maxV = 0

    for start_node in range(1, N + 1):
        visited[start_node] = 1
        number_of_vertex_dfs(graph, start_node, 1)
        visited = [0] * (N + 1)

    print("#{} {}".format(tc, maxV))