tistory에서 옮겨왔습니다
후기
좋은 테마의 문제들을 주로 뽑아왔다.
A번이 둘째가로 어려운 문제였는데,
맨 앞에 있다보니 다들 도전해주셨다. 덕분에 정답률이 매우 높다.
그리고, 나는 요즘 DP 공부가 한창이기 때문에 B번에 매달리다가 시간을 다 보내버렸다...ㅋ
그리고 사실 지금 난 CF Div.3를 풀고 있어야 하지만, D번 문제를 열심히 풀어서 제출했더니 문제가 수정되어있어서 틀렸다. 뇌절하고 그냥 BOJ 풀이를 작성하러 돌아왔다...(내 레이팅.............)
Ⓐ 케빈 베이컨의 6단계 법칙 (1389)
by dohoon
문제 분류를 보면 언뜻 플로이드 워셜이라고 되어있는 것을 볼 수 있는데,
사실 bfs로도 충분히 풀리는 문제라서 가져왔다.
코드가 약간 길어진 감은 있지만, 오늘따라 줄바꿈을 그냥 많이 하고 싶었을 뿐이다 ㅋㅋ!
저기 an은 ans의 잔재인데,
문제를 잘못 읽는 바람에 다른 것을 구해버려서 급하게 바꿔버렸다...
그래서 코드가 더러우니 설명은 책임지고 열심히 해보도록 하겠다.
일단, while (m--) 부분은 입력만 주구장창 받으면 된다. 중복된 경우가 존재할 수 있다고 하지만 아무런 상관이 없다. 왜냐하면 visited를 확인해서 거의 눈에 띄지 않을 정도로 빠른 속도로 넘겨버릴 수 있기 때문이다.
그 다음은 q와 visited, dist이다. 전형적인 bfs 구현 속 요소들이다.
그 다음 an은 최소를 표현하기 위해 int의 최대 범위인 로 잡았다. 가능하면 저정도는 외워두기를 권장한다.
그리고 ans, an이 새로운 최솟값이 되었을 때 그 경로의 시작 노드를 기록하는 역할이다. 궁극적으로 answer이니 ans.
for문을 통해 모든 노드에서부터 bfs를 이용하여 순회를 시작한다.
visited와 dist는 시작 노드에 따라서 매번 초기화를 진행하자.
q는 새로운 노드에서 이미 비워진 상태이므로 초기화의 필요가 없다.
그 다음은 전형적인 bfs 코드.
마지막은 구간의 합을 계산해주는 함수인 accumulate로 깔끔하게 마무리하면 된다.
Ⓑ
Ⓒ 끝말잇기 (20528)
by dohoon
취향껏 원하는 STL을 펼치면 풀 수 있다.
나는 erase+unique를 추천한다. 연속된 원소들은 하나로 치부해버리는 작업.
다른 방법은 댓글로 남겨주신다면 매우 감사할 겁이당!!
Ⓓ 숨바꼭질 (1697)
by dohoon
bfs 문제이다.
다음과 같은 그래프를 순회한다는 생각을 하면 된다.
배열 밖의 범위로 넘어가지는 않는가를 따져준다면 틀리기도 쉽지 않아 참 좋다.
Ⓔ 유니대전 퀴즈쇼 (20362)
by dohoon
간단한 구현 문제였습니다.
각자의 방식대로 구현해보기를 권장하지만, 일단 제 코드는 이렇습니다.
맵으로 묶어서 확인했지만, 사실 그 정도까지는 필요가 없고, 연습 겸 이 정도로 짜봤습니다.
