[Softeer 6차기출] 출퇴근길(python)

https://softeer.ai/practice/info.do?idx=1&eid=1529&sw_prbl_sbms_sn=212909 

Softeer

 

문제설명

BFS DFS를 사용한 길 찾기 문제.

하지만 조건이 은근 까다로운 편.

 

초기 코드(틀림)

from collections import deque



def bfs(start,end,graph):
    q=deque()
    q.append(start)
    v=[0]*len(graph)
    v[start]=1

    while q:
        now=q.popleft()
        if now==end:
            continue
        for go in graph[now]:
            if v[go]:
                continue
            if go==end:
                continue
            v[go]=1
            q.append(go)
    return v


n,m=map(int,input().split())

graph=[[]for _ in range(n+1)]

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

s,t=map(int,input().split())



d1=bfs(s,t,graph)
d2=bfs(t,s,graph)
answer=0
for i in range(n):
    if d1[i] and d2[i]:
        answer+=1

print(answer)

 

시작->도착

도착->시작

이렇게 2개의 케이스가 존재할 때

겹치는 경로를 구하면 된다고 생각했다.

하지만 오답이었고 이에 해설강의를 참고했다.

 

해설영상

https://www.youtube.com/watch?v=PAihI2CGr-M 

 

개선한 방법

 

S->T

T->S

까지는 생각하기 쉽지만

 

 

x->T

x->S

(x는 미지의 출발점)

이걸 계산해아한다는 게 머릿속으로 쉽게 받아드려지지 않았다.

"굳이 T나 S로 역으로 가는 케이스를 왜 구해야하지??"

 

문제의 조건을 읽어보면

"출근길 경로에서 S가 여러 번 나와도 되고

퇴근길 경로에서 T가 여러번 나와도 된다"

라고 되어있다.

즉, S가 여기저기 돌다가 다시 S로 돌아와서 T로 가는 경우

T에 갔다가 여기저기 들렸다가 T로 가는 경우

이 2가지 케이스가 더 존재한다.

초기의 방법은

S->T T->S 직행만 구했기 때문에 저런 케이스는 구하지 못했던 것.

그래서 S->T T->S포함

x->S x->T까지 고려해서

이 4가지 케이스에서 겹치는 정점의 갯수가 답이다.

 

정답코드

from collections import deque



def bfs(start,g,v):
    q=deque()
    q.append(start)
    v[start]=1
    while q:
        now=q.popleft()
        for go in g[now]:
            if v[go]:
                continue
            v[go]=1
            q.append(go)



n,m=map(int,input().split())

graph=[[]for _ in range(n+1)]
graph_re=[[]for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph_re[b].append(a)

S,T=map(int,input().split())

fromS=[0]*(n+1)
fromS[T]=1          # S->T 1로 미리 세팅
bfs(S,graph,fromS)

fromT=[0]*(n+1)
fromT[S]=1          # T->S 1로 미리 세팅

bfs(T,graph,fromT)

toS=[0]*(n+1)
bfs(S,graph_re,toS)

toT=[0]*(n+1)
bfs(T,graph_re,toT)
answer=0

for i in range(1,n+1):
    #출발,도착점은 무조건 한번만 지나는데, 이렇게 bfs돌리면 모든 곳에서 지난다고 뜸
    #그래서 출발,도착점은 건너뛰고 계산
    if i==S or i==T:
        continue
    if fromS[i] and fromT[i] and toS[i] and toT[i]:
        answer+=1

print(answer)

bfs로 푸는 게 익숙해서 이렇게 풀었는데

dfs로 푸는 풀이들이 많다.

그 이유는 마지막 정점 계산하는 지점에서

출발,도착 두 정점을 생각안하도 되기 때문.

실제로 bfs로 구현하고 나서 답이랑 계속 안맞아서 고생했는데,

x->T x->S를 구현하는 과정에서

T,S정점도 가능하다고 인식해버려서

원래 답보다 2씩 더 컸다.

https://khw11044.github.io/study/codingtest/2023-04-16-cote20/