[Softeer] HSAT 6회 정기 코딩 인증평가 기출 | 출퇴근길

문제링크

---

HSAT 6회 정기 코딩 인증평가 기출 | 출퇴근길

풀이과정

---

이 문제는 S에서 어떤 노드를 갈 수 있는데, T에서는 갈 수 있는가 ?를 판단하는게 핵심인 문제였던 것 같다.

어떻게 가냐고요 ? 그냥 T에서 거꾸로 가버리면 되지요 ㅎㅎ; 라는 마인드로 그래프 두개 만들어버렸다.

처음엔 dfs를 썼는데 메모리 초과가 떠서 bfs를 사용하니 정답처리 되었다 ... 재귀를 계속 돌아서 터진것 같긴 하다.


암튼! 4개의 방문 확인 배열을 만들건데, S, T에서 시작하고 도착하는 배열을 우르르 만들고 bfs를 통해 방문 가능한 노드를 1로 바꿔주자.

그리고 나서 4개의 방문 배열이 모두 1인 노드가 출/퇴근시 모두 방문 가능한 노드이므로 cnt를 증가시켜주고, 마지막에 2를 빼주면 된다.

2를 빼는 이유는 ? 당연히 시작점과 끝점은 무조건 방문처리가 되었기 때문에 이를 제외하고 값을 출력해주면 된다.

코드

---

1. 메모리 초과(dfs 사용)

import sys
sys.setrecursionlimit(10**8)
n, m  = map(int, sys.stdin.readline().split())

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

def dfs(graph, current, visited):
    if visited[current] == 1:
        return
    else:
        visited[current] = 1
        for node in graph[current]:
            dfs(graph, node, visited)

    return

for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    go_graph[x].append(y)
    back_graph[y].append(x)

S, T = map(int, sys.stdin.readline().split())

fromS, fromT, toS, toT = [[0] * (n+1) for _ in range(4)]
fromS[T] = fromT[S] = 1

dfs(go_graph, S, fromS)
dfs(go_graph, T, fromT)
dfs(back_graph, S, toS)
dfs(back_graph, T, toT)

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)

2. 통과 ! (bfs 사용)

import sys
sys.setrecursionlimit(10**8)
from collections import deque

n, m  = map(int, sys.stdin.readline().split())

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

for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    go_graph[x].append(y)
    back_graph[y].append(x)

S, T = map(int, sys.stdin.readline().split())

def bfs(graph, current, visited):
    q = deque([current])

    visited[current] = 1

    while q:
        x = q.popleft()
        for node in graph[x]:
            if not visited[node]:
                visited[node] = 1
                q.append(node)

fromS, fromT, toS, toT = [[0] * (n+1) for _ in range(4)]
fromS[T] = fromT[S] = 1

bfs(go_graph, S, fromS)
bfs(go_graph, T, fromT)
bfs(back_graph, S, toS)
bfs(back_graph, T, toT)

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)

결과

---