[백준] 2252번 - 줄 세우기 / 골드 3 / 파이썬 풀이

2022. 1. 23. 22:37·알고리즘 공부

문제 링크

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

 

2252번: 줄 세우기

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의

www.acmicpc.net


시간 제한
: 2초

메모리 제한 : 128 MB

 

문제 요약

  • N명의 학생들을 키 순서대로 줄을 세운것이다. (N은 입력으로 주어짐)
  • 두 학생의 키를 비교하는 방법을 사용할건데,
    N명의 학생들을 모두 비교한 것이 아니라, 일부 학생들의 키만 비교한다.
  • 키를 비교한 횟수 M (입력으로 주어짐)
  • 첫째줄 다음 M개의 줄에는 키를 비교한 두 학생의 번호가 주어지는데, 
    앞에 위치한 학생이 키가 더 작아서 앞에 서야 한다는 것을 의미함.
    ex) 1 3 => 1번이 3번보다 키가 작다. => 줄 서는 순서도 '1 3' 이 되어야 한다.

  • 문제 : 일부 학생들의 키만 비교하여, 전체 학생들의 키 순서대로 배치한 결과를 출력하라.

  • 종료 조건
    - 첫째줄을 제외한 M 개의 줄이 입력되면 프로그램 종료. (M 번의 비교)

 

입력

예제 입력 1

3 2
1 3
2 3

예제 입력 2

4 2
4 2
3 1

 

출력

예제 출력 1

1 2 3

예제 출력 2

4 2 3 1

풀이

 

"위상정렬! 키가 작은 놈은 더 이상 비교할 필요가 없다고 보고 진입차수를 -1 하여 최종적으로 0이 되게끔 한다."

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())       # n 명의 학생들  /  m 번의 키 비교 횟수

inDegree = [0] * (n+1)      # 진입차수(in-degree)가 0인 학생들을 큐에 넣을 것이다.
                            # (n+1을 한 이유는, 인덱스로 인해 헷갈리지 않기 위함.)
inDegree[0] = -1            # 0번째 인덱스는 -1로 초기화하여 위상 정렬 알고리즘에 영향 받지 않도록.

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

queue = deque()

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())   # 첫째줄 다음으로 입력받는 m 개의 줄에서, 두 학생의 키 비교가 된 결과 입력 받음.
    inDegree[b] += 1        # b가 키가 더 크므로, 다른 친구와 비교가 더 되어야 하니까, 진입차수가 늘어나는 것으로 한다.
    direct[a].append(b)     # 차수 확인을 위한 리스트 direct

for i in range(1, n+1):         # 진입차수가 0인 것을 뽑아내는 과정.
    if inDegree[i] == 0:
        queue.append(i)         # 진입차수가 0인 놈은 큐에 넣어둔다.

while queue:
    q = queue.popleft()         # 제일 먼저 큐에 들어온 놈이 키가 제일 작은 놈.
    print(q, end=' ')
    for d in direct[q]:
        inDegree[d] -= 1
        if inDegree[d] == 0:
            queue.append(d)

 

참고

https://sungmin-joo.tistory.com/83

 

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

출처 : https://www.acmicpc.net/problem/2252 입사 후 교육을 받는 기간이라 주말에 간간히 한 두 문제 정도 풀 수 있다..ㅜ 심지어 회사와 관련된 내용과 지식은 보안상 조심해야 한다고 하기 때문에 퇴사

sungmin-joo.tistory.com

https://blog.naver.com/ndb796/221236874984 - 위상 정렬 개념

 

25. 위상 정렬(Topology Sort)

위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 ...

blog.naver.com

 

'알고리즘 공부' 카테고리의 다른 글

[백준] 1958번 - LCS 3 / 골드 3 / 파이썬 풀이  (0) 2022.02.14
[백준] 1507번 - 궁금한 민호 / 골드 3 / 파이썬 풀이  (0) 2022.01.31
[백준] 9935번 - 문자열 폭발 / 골드4 / 파이썬 풀이  (0) 2022.01.12
[백준] 1915번 - 가장 큰 정사각형 / 골드4 / 파이썬 풀이  (0) 2022.01.11
[백준] 16236번 - 아기상어 / 골드4 / 파이썬 풀이  (0) 2021.12.21
'알고리즘 공부' 카테고리의 다른 글
  • [백준] 1958번 - LCS 3 / 골드 3 / 파이썬 풀이
  • [백준] 1507번 - 궁금한 민호 / 골드 3 / 파이썬 풀이
  • [백준] 9935번 - 문자열 폭발 / 골드4 / 파이썬 풀이
  • [백준] 1915번 - 가장 큰 정사각형 / 골드4 / 파이썬 풀이
코_노
코_노
일상의 불편함을 기술로서 해결하기 위해 노력하는 IT 엔지니어입니다. Contact point) jjh3706@gmail.com
  • 코_노
    코딩하는 주노 이야기
    코_노
  • 전체
    오늘
    어제
    • 코딩 이야기 (121)
      • DB (35)
        • SQL Server (MSSQL) (27)
        • MongoDB (2)
        • Hadoop Ecosystem (0)
        • SQLP 공부 (2)
      • 데이터 엔지니어링 (0)
        • Spark (0)
      • Middleware (21)
        • 웹서버 (7)
        • WAS (6)
        • WSGI (3)
        • 기타 (5)
      • OS (10)
        • Linux (7)
        • Windows (3)
      • Network (8)
      • Cloud (1)
        • AWS (1)
      • DevOps (8)
        • Container & K8S (0)
        • Github (3)
        • Ansible (2)
        • Terraform (3)
      • Security (3)
      • Observability (5)
      • CS 지식 | 기초 용어,개념 (7)
      • Python (1)
        • Flask (0)
      • Java (7)
        • JPA (0)
      • 안드로이드 (1)
      • 알고리즘 공부 (14)
  • 블로그 메뉴

    • 홈
    • 코딩 이야기
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    SQL Server 2019
    SAS
    백준 python
    SSMS
    백준 골드2
    db
    DBA
    백준 골드4
    백준 알고리즘
    Windows AD
    백준 파이썬
    SQL Server 2019 Restore
    jvm 실행 옵션
    백준 골드 2
    SQL Server
    MongoDB Sharding
    SAS Intelligence Platform
    MSSQL
    백준
    SAS 아키텍처
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.6
코_노
[백준] 2252번 - 줄 세우기 / 골드 3 / 파이썬 풀이
상단으로

티스토리툴바