[Softeer] 출퇴근길 (level 3)

사용 언어: Python3

문제

출퇴근길

풀이

내 풀이 - 출퇴근길 경로 저장

import sys
from copy import deepcopy

def DFS(v, dest, tmpPath): # 시작 노드 # 도착 노드 # 출근길 혹은 퇴근길 경로
    if v == dest:
        tmpPath.append(deepcopy(path)) # ✅ deepcopy
    else:
        for i in range(1, N+1):
            if visited[i] > 1: # ✅ 한 번까지는 왔다갔다 가능
                continue
            if G[v][i] == 1:
                path.append(i)
                visited[i] += 1
                DFS(i, dest, tmpPath)
                path.pop()
                visited[i] -= 1

N, M = map(int, input().split())
G = [[0] * (N+1) for _ in range(N+1)]
for _ in range(M):
    s, e = map(int, input().split())
    G[s][e] = 1
S, T = map(int, input().split())

goPath = [] # ✅ 출근길 경로
path = [] # tmp path
visited = [0] * (N+1)
path.append(S)
# visited[S] = 1 # 사실 안해도 됨
DFS(S, T, goPath) # 출근: 집에서 시작, 회사 도착

backPath = [] # 퇴근길 경로
path.clear()
visited = [0] * (N+1)
path.append(T)
DFS(T, S, backPath) # 퇴근

res = [-1] * (N+1) # 출퇴근길 공통 동네 찾기
for x in goPath:
    for val in x:
        res[val] = 1
for x in backPath:
    for val in x:
        if res[val] == 1:
            res[val] = 0

print(res.count(0) - 2) # 집, 회사 제외

• 실패

내 풀이 - 경로 저장 X

import sys

# 출근길에 지나간 노드 체크
# (출근길에 지나갔으면서) 퇴근길에 지나간 노드 체크
def DFS(v, dst, flag): # v는 시작 노드 # flag: 출근(0) / 퇴근(1)
    if v == dst:
        return
    elif flag == 0: # ✅ 출근
        for i in range(1, N+1):
            if visited[i] > 1: # ✅ 한번은 왔다갔다
                continue
            if G[v][i] == 1:
                visited[i] += 1 # ✅
                res[i] = 1 # 출근길에 방문
                DFS(i, dst, 0) # 출근
                visited[i] -= 1 # ✅
    elif flag == 1: # ✅ 퇴근
        for i in range(1, N+1):
            if visited[i] > 1: # ✅ 한번은 왔다갔다
                continue
            if G[v][i] == 1:
                visited[i] += 1 # ✅
                if res[i] == 1: # 출근길에 방문한 동네를
                    res[i] = 0 # 퇴근길에 방문
                DFS(i, dst, 1) # 퇴근
                visited[i] -= 1 # ✅

N, M = map(int, input().split())
G = [[0] * (N+1) for _ in range(N+1)]

for _ in range(M):
    s, e = map(int, input().split())
    G[s][e] = 1

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

visited = [0] * (N+1)
res = [-1] * (N+1) # 출퇴근길 모두 방문한 동네 체크용
# 출근길
DFS(S, T, 0)

# 퇴근길
visited = [0] * (N+1)
DFS(T, S, 1)

print(res.count(0) - 2) # 집 회사 제외

• 실패

다른 풀이

import sys
sys.setrecursionlimit(10**6) # ✅ 넉넉히 100만으로 설정 (안하면 런타임 에러)

def DFS(v, A, visited): # v: 노드, A: 인접행렬(adj/adjR)
    if visited[v] == 1:
        return
    visited[v] = 1
    for x in A[v]:
        DFS(x, A, visited)
    return 

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)] # 인접행렬
adjR = [[] for _ in range(N+1)] # 반대 방향

for _ in range(M):
    s, e = map(int, input().split())
    adj[s].append(e)
    adjR[e].append(s)

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

# S -> v
fromS = [0] * (N+1) # S에서 v로 visited
fromS[T] = 1 # 출근길에서 T를 만나면 stop
DFS(S, adj, fromS)

# T -> v
fromT = [0] * (N+1) # T에서 v로 visited
fromT[S] = 1 # 퇴근길에서 S를 만나면 stop
DFS(T, adj, fromT)

# v -> S
toS = [0] * (N+1) # v에서 S로 visited
DFS(S, adjR, toS) # 방향을 바꿔서 S에서 출발

# v -> T
toT = [0] * (N+1) # v에서 T로 visited
DFS(T, adjR, toT) # 방향을 바꿔서 T에서 출발

cnt = 0
for i in range(1, N+1):
    if fromS[i] and fromT[i] and toS[i] and toT[i]:
        cnt += 1
print(cnt - 2) # 집 회사 제외

• 출퇴근길에 모두 방문 가능하려면
  • 특정 노드(=v)가 있을 때
  • S에서 v까지 접근 가능 && v에서 T까지 접근 가능 && T에서 v까지 접근 가능 && v에서 S까지 접근 가능 해야 한다.
    • 이때 S에서 v까지와 T에서 v까지는 DFS 사용
    • v에서 S까지와 v에서 T까지는 그래프 방향을 바꿔서 DFS 사용
• 강의 참고

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기