plzrun   3년 전

bfs 위상정렬로 구현했습니다.

위상정렬 하던도중 큐가 완전히 비게 되면 !

큐 사이즈가 2이상이 되면 ?

무사히 다 통과하면 위상정렬이 완료된 것으로 하였습니다.


근데 어디가 문제일까요 ㅠㅠ?

도와주세요 ㅠㅠ

plzrun   3년 전

doju님이 알려주셔서 풀 수 있었습니다.
혹시 계속 틀리는데 왜 틀리는지 이해가 안가시는 분들을 위해 테케를 남겨드리자면,

2
abc
ab

이걸 잘 처리하는지 한번 봐보세요.
s[i-x]에 해당하는 스트링이 s[i] 스트링과 prefix가 겹치는데 s[i-x]의 길이가 더 큰경우 반드시 !를 출력해야 해요.
그런데 저 같은 경우는 위/아래 단어만 비교하면서 그래프를 만들었더니 문제가 생겼네요.

pwr2011   3달 전

안녕하세요 궁금한게 있어서 답글을 답니다

2
abc
ab

이런 input이 들어올 수 있다고 하셨는데, 문제의 설명에서 사전순으로 정렬된 input이 들어온다고 했습니다.

저건 사전순으로 들어온게 아니지 않나요? 예를 들어 배 -> 배편 으로 사전이 정렬되어지지 배편->배 순서로 정렬이 되지는 않는것 처럼요.

감사합니다.

parkpkww   1달 전

" 올바른 순서가 없다면 "!"를, 가능한 순서가 한 개 이상이라면 "?"를 출력한다. "라고 문제를 주고 있습니다.

즉, 배편 -> 배 순서로 입력이 주어지는 경우 "!" 를 출력해주면 될 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.