huh0918   1년 전

케이스를 큐에 받은다음,

앞에서부터 pop해가며 유효한지 체크하는 로직입니다 

첫 숫자(1)#?# 우선 큐애 그냥 넣고;

그 다음 부터는, 큐에서 팝한거와 인접하고 아직 방문하지 않은 것들을 전부 넣습니다. (set의 find를 활용해서 인접한지 여부 체크)

만약, 순서대로 인접한 것들을 다 넣었는데 pop한 정점에서 연결된 정점중에, 아직 방문하지 않은게 있다면 그 케이스는 잘못됐다는 로직입니다.

간절하게 지적 부탁드립니다 ㅠㅠ

amsminn   1년 전

인접한 것을 pop하는 순서도 중요합니다. 

a->b

a->c

b-> {d, e, f}

c-> {g, h, i} 

간선이 있을 때 

{d, e, f}, {g, h, i}가 섞이면 안됩니다.

huh0918   1년 전

댓글써주셔서 감사합니다. 그 문제는 큐를 사용해서 해결했다고 생각했었습니다.

주신 예를 그대로 사용하면,

우선 a가 큐에나갔다 들어오면서,

다음입력은 b와 c가 있어야 합니다.(순서무관) 만약 연속으로 있지 않으면 0을 출력하고 끝날겁니다.

c가 먼저있었다고 가정하면, c와b가 둘다 큐에 들어가지만 c가 먼저 들어갑니다. 

c가 팝되면서, 다음엔 c와 인접한 자식 세개가 있어야합니다. (순서무관, 마찬가지로 연속으로 안나올 시, 0출력) 그것들을 순서대로 큐에 넣고, 그 다음엔 b를 팝하고 b의 자식 세개가 연속으로 남아있을것으로 기대하면서 큐에 넣습니다.

ans에 남은 

huh0918   1년 전

해결했습니다.

첫 입력이 뭐가 들어오든 거기서부터 bfs를 수행했습니다. 로직은 틀린 게 없었습니다.

설마하고, 첫 입력이 1이 아닌 경우 그냥 바로 0을 출력하고 끝내도록 코드 두줄을 추가하니깐.. 맞았습니다. 

이상입니다.

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