인프런 커뮤니티 질문&답변
작성한 질문수
3-I질문 있습니다
작성
·
53
·
수정됨
0
http://boj.kr/aafa9c1e2c3843a2852b34b61bcadf37
안녕하세요 큰돌님 공부를위해 기존에 풀이했던 문제를 다시 처음부터 풀면서 강의를 다시 시청하고있습니다.
오랜만에 다시 알고리즘 공부를 하려고 강의를 열었는데 추가된 교안과 추가영상등 양질의 강의가 더욱 업그레이드되어 감사함을느낍니다.
다시풀어도 플레티넘문제는 아이디어에서 자잘하게막히는 부분이 생겨 궁금증을 해결하기위해 질문을 남겼습니다.
수빈이가 time만큼 이동하면서 해당범위를 최단탐색(bfs)를 통해 기록하면서 동생의 이동위치와 겹치는 부분이 생기면 홀수/짝수에 관계없이 +2초의 시간을 이용해 수빈이는 해당위치에 고정해서 대기 할 수 있기 때문에 방문배열(visited)를 홀수/짝수로 구분해 k(동생의위치)를 체크하면서 범위탐색을 형제노드(탐색시 queue의 원소들)을 순서대로 체크한다는 아이디어 까지는 이해를 했다고 생각합니다.
이때 두가지가 큰돌님코드에서 이해가안가는데
첫째로 visited의 탐색체크를 (turn+1) %2 = turn%2 +1
로 체크를 안하고 반대로 체크하시는부분,
두번째로 다음위치(nx)와 동생위치(b)만을 비교, 반복문을 탈출하는 부분이 있는데 위치만을 비교하면 안되고 방문시의 홀수/짝수도 같이 구분이 완료되야만 체크가 완료된게아닌가요? 그래서 제가 제출한 코드에서는 짝수/홀수 체크가 끝난 동생방문타이밍에서만 체크가 확인되면 조건체크후 탐색을 종료하게끔 작성했는데 예시코드에서 위에언급한 두부분이 이해가 잘 안가네요 답변해주시면 감사하겠습니다.
답변 1
0
안녕하세요 선용님 ㅎㅎ
오랜만에 다시 알고리즘 공부를 하려고 강의를 열었는데 추가된 교안과 추가영상등 양질의 강의가 더욱 업그레이드되어 감사함을느낍니다.
>> ㅎㅎ 제 노력을 알아주셔서 감사합니다.
이때 두가지가 큰돌님코드에서 이해가안가는데
첫째로 visited의 탐색체크를 (turn+1) %2 = turn%2 +1
-> 이거는 visited[next] = visited[now] + 1을 생각해주시면 됩니다.
예를 들어 지금 2초에 방문했다면 그 전에는 1초.
즉 그 다음이 홀수번째라면 그 전에는 짝수번째임은 자명합니다.
홀수 = 짝수 + 1
이렇게 보시면 됩니다.
두번째로 다음위치(nx)와 동생위치(b)만을 비교, 반복문을 탈출하는 부분이 있는데 위치만을 비교하면 안되고 방문시의 홀수/짝수도 같이 구분이 완료되야만 체크가 완료된게아닌가요?
->
if(nx == b){
ok = 1; break;
}이부분이죠?
먼저 홀짝의 구분은 수빈이가 1초에 왔을 때 동생이 3초에 오는 경우를 대비한 부분입니다. 즉 수빈이가 전에 왔고 그 다음 동생이 그 이후에 왔을 때는 그 짝홀의 구분이 필요합니다.
nx == b 부분은 동생이 간다 : b = b + turn / 그부분에서 수빈이가 움직이는 경우의 수 nx와 비교해서 지금! 수빈이와 동생이 만나는지를 판단하는 것이기 때문에 짝홀의 구분은 필요없습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
음.. 왜 홀짝이 구분이 되어야 하나요?
그래서 제가 제출한 코드에서는 짝수/홀수 체크가 끝난 동생방문타이밍에서만 체크가 확인되면 조건체크후 탐색을 종료하게끔 작성했는데 예시코드에서 위에언급한 두부분이 이해가 잘 안가네요 답변해주시면 감사하겠습니다.