TIL 2019-08-27
오늘 배운 것 & 한 것
sport
백준 16137 - 견우와 직녀
https://www.acmicpc.net/problem/16137
다리를 연속해서 건너서는 안 된다는 조건 때문에 여러 번 틀림. 다 풀었다고 생각되더라도 다시한번 모든 조건을 구현했는지 확인해야겠다. 아니면 처음부터 다양한 조건들을 나타내는 테스트 케이스들을 하나씩 만들어 보는게 좋을수도.
bfs로는 구현하기 까다롭다고 생각했는데 (주기 다리 건너기 때문에) 검색해보니 bfs로 구현한 사람이 있었다. 다리 사용의 유무 때문에도 bfs로 구현하기 어렵다고 생각했지만 bfs로 구현한 코드가 있다. 그 경우 이전 정보에 대해 필요한 유일한 정보인 이전 위치가 절벽이었는지에 대한 정보를 탐색할 때 얻기 위해, 현재 상태 정보에 현재 위치가 절벽인지에 대한 여부를 상태 정보에 넣는다. 또, 탐색 거리를 건너뛰는 문제에 대한 점은 bfs에서도 visited여부만으로 갱신하는 게 아니라, cost를 더 줄일 수 있으면 탐색함으로써 구현 가능하다.
tags
#sport, #blog
Comments