13549번 - 숨바꼭질 3
가중치 값이 0 또는 1을 가지므로
0-1 BFS로 풀어보려고 했습니다.
가중치가 1인 앞으로 이동, 뒤로 이동하는 경우 queue의 맨 뒤로 보내고,
가중치가 0인 순간이동은 queue의 맨 앞으로 보냈습니다.
아래와 같은 흐름으로 코드를 작성했습니다.
queue에 맨 처음 시작하는 수를 넣는다.
while(queue가 비어있지 않을 동안) {
now <- 현재 위치
if(앞으로 이동시 범위내에 있는가?) {
if(처음 넣는가? or 이전 가중치 값보다 더 작은가?) {
다음 탐색할 수로 queue의 맨 뒤로 보낸다.
해당 위치에 대한 최소 가중치 값을 갱신한다.
}
if(뒤로 이동시 범위내에 있는가?) {
if(2배로 순간 이동할 시 범위내 있는가?) {
다음 탐색할 수로 queue의 맨 앞으로 보낸다.
바쁘신 와중에 긴 글 읽어 주셔서 감사합니다.
여러번 고민하고, 여러 반례로 테스트했지만, 혼자서 잘 안되는 것 같습니다.ㅠㅠ
s == e일 때 0을 출력하게만 하면 통과됩니다.
계속해서 고민했는데... 정말 감사합니다!!!😊
댓글을 작성하려면 로그인해야 합니다.
backstone 1년 전
가중치 값이 0 또는 1을 가지므로
0-1 BFS로 풀어보려고 했습니다.
가중치가 1인 앞으로 이동, 뒤로 이동하는 경우 queue의 맨 뒤로 보내고,
가중치가 0인 순간이동은 queue의 맨 앞으로 보냈습니다.
아래와 같은 흐름으로 코드를 작성했습니다.
queue에 맨 처음 시작하는 수를 넣는다.
while(queue가 비어있지 않을 동안) {
now <- 현재 위치
if(앞으로 이동시 범위내에 있는가?) {
if(처음 넣는가? or 이전 가중치 값보다 더 작은가?) {
다음 탐색할 수로 queue의 맨 뒤로 보낸다.
해당 위치에 대한 최소 가중치 값을 갱신한다.
}
}
if(뒤로 이동시 범위내에 있는가?) {
if(처음 넣는가? or 이전 가중치 값보다 더 작은가?) {
다음 탐색할 수로 queue의 맨 뒤로 보낸다.
해당 위치에 대한 최소 가중치 값을 갱신한다.
}
}
if(2배로 순간 이동할 시 범위내 있는가?) {
if(처음 넣는가? or 이전 가중치 값보다 더 작은가?) {
다음 탐색할 수로 queue의 맨 앞으로 보낸다.
해당 위치에 대한 최소 가중치 값을 갱신한다.
}
}
}
바쁘신 와중에 긴 글 읽어 주셔서 감사합니다.
여러번 고민하고, 여러 반례로 테스트했지만, 혼자서 잘 안되는 것 같습니다.ㅠㅠ