[Python] SWEA 4871: 그래프 경로

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AYYF1QaaEvoDFAVw&contestProbId=AYKpirUagmkDFASv&probBoxId=AYZNijtKNMMDFAVw&type=USER&problemBoxTitle=230214+%EC%8A%A4%ED%83%9D1&problemBoxCnt=4 

SW Expert Academy

DFS 알고리즘을 이용해서 푸는 문제.

V개의 노드를 E개의 간선으로 연결하고, 특정한 두 개의 노드가 경로에 존재하는지를 묻는 문제.

문제에서 중요한 점은 경로를 묻는 문제라는 것이다.(방향성 그래프라는 점을 염두해야 한다.)

 

DFS 알고리즘을 처음 배웠는데, 여러 방법을 알려주셨고, 그 방법을 통해 풀면 되는 문제였지만 내 것이 아닌 상태로 풀려니 더욱 헷갈렸다. 이 방법을 했다가 안 되면 다른 방법을 써보고... 의 반복이였다.

 

1차 시도

당연히 안 풀렸다. 교량 하나하나를 리스트로 받아왔고, 그 교량을 통해 경로를 구하고자 했으나... 틀렸다. 그냥 애초에 접근 자체를 잘못해서 인덱스 에러가 떴다.

 

TC #2를 넣어보면

[[], [1, 6], [2, 3], [2, 6], [3, 5]] 와 같은 ls가 뜨는데, 생각해보면 6번 땅까지 갈 수 있는 인덱스 자체가 만들어지지 않아서 경로를 구하는 것도 불가능할 뿐더러 나중에 봤을 때 무슨 말을 하는건지? 싶을 거 같다.(문제 푼지 1시간 지난 지금도 그렇다.)

def dfs(S,E):
    ST = []
    visited = [False] * (V+1)

    ST.append(S)
    visited[S] = True
    while ST:
        v = ST.pop()
        if v==E:
            return 1
        for w in ls[v]:
            if not visited[w]:
                ST.append(w)
                visited[w] = True
    return 0

T = int(input())

for tc in range(1,T+1):
    ls =[[]]
    V,E = map(int, input().split())
    for i in range(E):
        ls.append(list(map(int, input().split())))
    A,B = map(int, input().split())
    print(ls, len(ls))
    print(f'#{tc} {dfs(A,B)}')

 

 

2차 시도

ls 자체를 잘못 만들었다는 것을 알고, 교량을 묶어서 리스트화 하는 것이 아니라 한 땅과 연결된 다른 땅의 번호를 리스트화 하려고 했다. 

[[], [1, 6], [2, 3], [2, 6], [3, 5]] #1번째 시도에서의 G-list

[[], [6], [3, 6], [2, 5], [], [3], [1, 2], []] #2번째 시도에서의 G-list

첫 번째 시도는 아예 접근 자체를 잘못했었다는 것을 알 수 있다. 내가 뽑아내고 싶었던 list는 2번이다. 

 

그러나 test를 해봤을 때 12개의 TC 중 8개가 틀렸다는 것을 알게 되었고, 다른 문제가 아니라 방향을 고려하지 않아 틀렸다는 것을 알게 되었다. G_list[v1].append(v2) 와 G_list[v2].append(v1) 두 번을 하게 되어 왕복을 고려하게 되는 것이다!

따라서 둘 중 하나의 경우만 고려해주면 된다.

def dfs(S,E):
    ST = []
    visited = [False] * (V+1)

    ST.append(S)
    visited[S] = True
    while ST:
        v = ST.pop()
        # if v==E:
        #     return 1
        for w in G_list[v]:
            if not visited[w]:
                if w==E:
                    return 1
                ST.append(w)
                visited[w] = True
    return 0


T = int(input())

for tc in range(1,T+1):
    ls = []
    V,E = map(int,input().split())
    for i in range(E):
        e1, e2 = map(int, input().split())
        ls.append(e1)
        ls.append(e2)
    S,G = map(int, input().split())
    G_list = [[] for _ in range(V+1)]
    for idx in range(0,len(ls), 2):
        v1 = ls[idx]
        v2 = ls[idx+1]
        G_list[v1].append(v2)
        G_list[v2].append(v1)
    # print(G_list)
    print(f'#{tc} {dfs(S,G)}')

 

ANS

def dfs(S,E):
    ST = []
    visited = [False] * (V+1)

    ST.append(S)
    visited[S] = True
    while ST:
        v = ST.pop()
        if v==E:
            return 1
        for w in G_list[v]:
            if not visited[w]:
                ST.append(w)
                visited[w] = True
    return 0


T = int(input())

for tc in range(1,T+1):
    ls = []
    V,E = map(int,input().split())
    for i in range(E):
        e1, e2 = map(int, input().split())
        ls.append(e1)
        ls.append(e2)
    S,G = map(int, input().split())
    G_list = [[] for _ in range(V+1)]
    for idx in range(0,len(ls),2):
        v1 = ls[idx]
        v2 = ls[idx+1]
        G_list[v1].append(v2)

    print(f'#{tc} {dfs(S,G)}')

참고로 #TC2에서 나온 G_list는 다음과 같다. [[], [6], [3, 6], [5], [], [], [], []]

이러한 경우만 고려하라고 했으니 G_list를 맞게 뽑아냈다는 것을 알 수 있다.

 

🔑

개념을 내 것으로 만들지 못하고 풀면 효율도 훨씬 덜 생기고, 문제를 풀어도 남의 코드를 그대로 가져다 쓴 느낌을 자주 받는다. 비슷한 문제라도 꼼꼼히 읽어보고, 암기해야 하는 개념은 암기하며 개념을 완전히 내 것으로 숙지한 후 문제에 재접근할 예정이다.