21937번: 작업
민상이가 작업할 개수 $N$와 작업 순서 정보의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째줄부터 $M + 1$ 줄까지 작업 $A_i$와 작업 $B_i$가 공백으로 구분되어 주어진다. 이때 두 값의 의미는 작
www.acmicpc.net
문제
민상이는 자신이 해야할 작업 개를 아래와 같이 작업 순서도로 그려보았다.
위 그림에서 5번 작업을 하기 위해 제일 먼저 2번 작업을 끝내야 하고 그 다음으로 4번 작업을 끝내야 5번 작업을 할 수 있다. 3번 작업은 먼저 해야하는 작업이 없으므로 3번 작업을 바로 시작 할 수 있다.
작업 순서를 정할때 위배되는 작업 순서는 없다. 예를 들어, A 작업을 하려면 B 작업을 먼저 해야하고, B 작업을 해야하기 전에 A 작업을 해야하는 상황은 없다.
민상이는 오늘 반드시 끝낼 작업 가 있다. 민상이가 작업 을 끝내기 위해서 먼저 해야하는 작업의 개수를 구해주자!
입력
민상이가 작업할 개수 와 작업 순서 정보의 개수 이 공백으로 구분되어 주어진다.
두 번째줄부터 줄까지 작업 와 작업 가 공백으로 구분되어 주어진다. 이때 두 값의 의미는 작업 를 하기 위해서 바로 이전에 작업 를 먼저 해야한다는 의미이다. 중복된 정보는 주어지지 않는다.
마지막 줄에는 민상이가 오늘 반드시 끝내야하는 작업 가 주어진다.
출력
민상이가 작업 를 하기 위해 먼저 해야하는 일의 개수를 출력한다.
제한
코드
- DFS
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
graph[b].append(a)
x = int(input())
ans = 0
visited = [False] * (n+1)
def dfs(now):
global ans
visited[now] = True
for nx in graph[now]:
if not visited[nx]:
ans += 1
dfs(nx)
dfs(x)
print(ans)
- BFS
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
graph[b].append(a)
x = int(input())
visited = [False] * (n+1)
visited[x] = True
q = deque([x])
ans = 0
while q:
now = q.popleft()
for nx in graph[now]:
if not visited[nx]:
q.append(nx)
visited[nx] = True
ans += 1
print(ans)
순서가 있는 그래프라고 해서 처음에는 위상정렬로 풀어야하는줄 알았는데 그냥 끝낼 작업 x에서 그래프 탐색을 해서 지나간 노드의 개수를 세면 되는 문제였다. DFS, BFS 둘 다 사용 가능하다.
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 3980번 선발 명단 (0) | 2023.08.27 |
---|---|
[Python/파이썬] 백준 17471번 게리맨더링 (0) | 2023.08.26 |
[Python/파이썬] 백준 17090번 미로 탈출하기 (0) | 2023.08.17 |
[Python/파이썬] 백준 18404번 현명한 나이트 (0) | 2023.08.17 |
[Python/파이썬] 백준 1520번 내리막 길 (0) | 2023.07.31 |