프레임 > 문제은행



문제은행

1100 : 프레임

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 3 회    시도횟수: 14 회   



아래와 같이 다섯 개의 액자 틀을 생각해 보자

........ ........ ........ ........ .CCC....
EEEEEE.. ........ ........ ..BBBB.. .C.C....
E....E.. DDDDDD.. ........ ..B..B.. .C.C....
E....E.. D....D.. ........ ..B..B.. .CCC....
E....E.. D....D.. ....AAAA ..B..B.. ........
E....E.. D....D.. ....A..A ..BBBB.. ........
E....E.. DDDDDD.. ....A..A ........ ........
E....E.. ........ ....AAAA ........ ........
EEEEEE.. ........ ........ ........ ........

    1         2          3         4         5

 

이제 이 액자들을 포갠다고 생각해 보자. 1번이 가장 아래로 5이 가장 위로 올라온다. 액자가 겹치면 위에 놓이는 액자 뒤의 액자를 가린다.

.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..

 

위 그림에서 어떤 액자가 위에 놓이는지 순서를 정하면 아래와 같다.
EDABC.

 

액자가 놓인 그림을 가지고 위의 순서를 정하는 프로그램을 작성하라.
1. 액자의 폭은 1이다. 액자의 크기는 가로, 세로 모두 3칸 이상이다.
2. 액자가 가려지더라도 액자의 네 변은 모두 보인다. 꼭지점은 두 변을 보여주는 것이다.
3. 액자는 대문자 알파벳으로 나타나고 두 액자가 같은 문자를 갖지 않는다.


먼저 그림의 높이 h (h<=30), 폭 w (w<=30)이 주어진다. 다음 줄부터 그림이 주어진다.



모든 가능한 순서를 출력해야 한다. 사전 순으로 출력해야 한다. 모든 입력에는 가능한 순서가 하나 이상 존재한다. 모든 출력 사이에는 공백 줄이 없어야 한다.


8 8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..
EDABC





topological sort(위상정렬), graph(그래프)

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.