백준 2252 [줄 세우기] 파이썬

https://www.acmicpc.net/problem/2252

 

 

DFS를 이용한 위상정렬

# 백준 2252 줄 세우기 - DFS(후위 순회) 기반 위상정렬
import sys
from collections import deque
sys.setrecursionlimit(10**6)  # 재귀 깊이 제한 확장 (최대 N=32,000일 수 있어서)
input = sys.stdin.readline

# N: 학생 수, M: 키 비교 횟수
N, M = map(int, input().split())

ans = deque()  # 위상정렬 결과를 저장할 덱(스택처럼 사용)

# DFS 함수 (후위 순회 방식)
def dfs(node):
    visited[node] = True  # 현재 노드를 방문 처리
    # 현재 노드보다 뒤에 서야 하는 노드(자식)들을 먼저 탐색
    for c_node in next_child[node]:
        if not visited[c_node]:
            dfs(c_node)
    # 모든 자식 노드를 처리한 뒤 현재 노드를 결과에 추가
    ans.append(node)

# 방문 여부 배열
visited = [False for _ in range(N+1)]

# 인접 리스트: next_child[A] = [B1, B2, ...]  (A가 B들보다 앞에 서야 함)
next_child = [[] for _ in range(N+1)]

# 키 비교 정보 입력
for _ in range(M):
    A, B = map(int, input().split())
    next_child[A].append(B)  # A → B 간선 추가

# 1번 학생부터 N번 학생까지 모두 확인
for i in range(1, N+1):
    if not visited[i]:  # 아직 방문 안 한 경우만 DFS 수행
        dfs(i)

# DFS 후위 순회의 결과(ans)는 역순이므로 뒤집어서 출력
ans.reverse()
print(*ans)

 

DFS를 이용하여 문제를 해결하려하였는데, 메모리 초과가 발생하였다.

위상정렬을 이용하여 해결하려고 했으나 구현의 문제로 GPT의 도움을 받아 해결하였다..

위상정렬 아직 익숙친 않다..

 

BFS를 이용하여 해결한 코드도 첨부한다.

# 백준 2252 줄 세우기 - BFS 기반 위상정렬 (Kahn's Algorithm)
import sys
from collections import deque
sys.setrecursionlimit(10**6)  # (BFS에서는 사실 불필요하지만 습관적으로 추가)
input = sys.stdin.readline

# N: 학생 수, M: 키 비교 횟수
N, M = map(int, input().split())

ans = deque()  # 위상정렬 결과 저장
graph = [[] for _ in range(N+1)]     # 인접 리스트 (graph[A] = A보다 뒤에 서야 하는 학생 목록)
in_degree = [0 for _ in range(N+1)]  # 각 노드의 진입 차수(앞에 서야 하는 학생 수)
visited = [False for _ in range(N+1)]# 방문 여부 체크 (중복 방지용)

# 키 비교 정보 입력
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)  # A → B 방향 간선 (A가 B보다 먼저)
    in_degree[B] += 1   # B의 진입 차수 증가

# 1번 학생부터 N번 학생까지 확인
for i in range(1, N+1):
    # 진입 차수가 0이면, 즉 앞에 서야 할 학생이 없으면 큐에 추가
    if in_degree[i] == 0 and not visited[i]:
        visited[i] = True
        q = deque()
        q.append(i)
        ans.append(i)

        # BFS 시작
        while q:
            node = q.popleft()
            # 현재 학생 뒤에 서야 하는 학생들 탐색
            for next_node in graph[node]:
                if not visited[next_node]:
                    in_degree[next_node] -= 1  # 연결된 간선 제거
                    if in_degree[next_node] == 0:  # 앞에 설 학생이 더 이상 없으면
                        visited[next_node] = True
                        ans.append(next_node)  # 결과에 추가
                        q.append(next_node)    # 큐에 넣어 다음 처리

# 위상정렬 결과 출력
print(*ans)

GPT가 좀 더 깔끔하게 정리해줬다.

 

각 node에 대해 in_degree=0 일때 바로 q에 넣어 BFS를 돌리는게 아니라

 

모든 노드들에 대해 in_degree=0인 값들을 q에 넣어 BFS를 한번에 돌리면 된다.

 

# 백준 2252 줄 세우기 - BFS 위상정렬 (visited 제거 버전)
import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]     # 인접 리스트
in_degree = [0] * (N+1)              # 진입 차수 배열

# 그래프 입력
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)  # A → B 간선
    in_degree[B] += 1   # B의 진입 차수 증가

# 진입 차수 0인 노드를 큐에 추가
q = deque()
for i in range(1, N+1):
    if in_degree[i] == 0:
        q.append(i)

# BFS 수행
ans = []
while q:
    node = q.popleft()
    ans.append(node)
    # 현재 노드의 모든 인접 노드에 대해
    for nxt in graph[node]:
        in_degree[nxt] -= 1  # 간선 제거
        if in_degree[nxt] == 0:
            q.append(nxt)

# 결과 출력
print(*ans)