백준 2252번 줄 세우기

문제 설명

이번 문제는 일부 학생의 키를 비교한 정보가 주어질 때, N명의 학생들을 키 순서대로 줄 세우는 방법을 구하는 문제입니다.

(답이 여러가지일 경우 한 가지만 출력해줍니다.)

 

문제 풀이

아이디어

줄을 서는 순서

입력으로 A B가 주어졌을 경우 B는 무조건  A 뒤에 있어야 하므로, B가 줄에 서기 위해 {A가 줄에 먼저 서야 된다}는 전제조건이 생깁니다. (줄을 앞에서부터 선다고 가정했습니다.). 

 

만약 B보다 앞에 와야하는 사람이 A 한 명이고 현재 A가 줄을 서게 된다면, B는 이후 어느 곳이든 줄을 서도 됩니다.

만약 B보다 앞에 와야하는 사람이 A와 C일 경우, A와 C가 모두 줄을 서야지만 B가 줄에 설 수 있게 됩니다.

 

풀이

변수

followed[N][] = 자신의 뒤에 오는 사람을 저장하는 2차원 배열입니다.

isFollowing[N] = 자신보다 앞 서 줄을 서야하는 사람의 수를 저장합니다.

visited[] = 줄에 이미 섰을 경우 True, 아직 줄에 서지 않았다면 False입니다.

result = 줄을 서는 순서를 저장하는 배열입니다.

 

반복

1번부터 N번까지 반복하며 아래 조건을 확인합니다.

• 이미 방문한 노드일 경우 해당 노드는 넘어갑니다.
• 자신보다 뒤에 와야하는 사람이 없고 자신보다 앞에 줄 서야하는 사람이 없다면 result 배열에 넣어주고 해당 노드는 넘어갑니다.

 

dfs

위 반복문에서 만족하는 조건이 없을 경우 해당 번호부터 dfs를 실행합니다.

stack에서 pop된 번호의 사람(num)이 자신보다 뒤에 와야하는 사람(nextNum)이 존재할 경우, 해당 사람의 isFollowing[nextNum]을 1 빼줍니다.

그리고 isFollowing[nextNum]이 0일 경우 해당 사람은 자신보다 앞 서 줄을 서야하는 사람이 모두 줄을 선 경우이므로 바로 result 배열에 넣어주고 visited[nextNum]도 True로 바꿔줍니다. 또한 stack에 nextNum을 append 해주어 nextNum을 따르는 사람을 줄 세울 수 있도록 해줍니다.

 

반복문이 끝나게 되면 모든 사람이 result 배열을 줄을 서 있게 됩니다. 이 배열을 출력해줍니다.

 

해결

이번 문제는 줄에 먼저 서야 되는 사람을 전제조건으로 만들고 이 전제조건을 어떤식으로 표현하고 해결해나갈지 생각해보는 문제였습니다.

 

문제 링크 : https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/2252.py