24.01.01 14:57 작성
·
272
0
해당 강의가 없어 직접 질문 하게 되었습니다.
2251번 책을 보면 이동 가능한 경로가
A -> B, A ->C, B -> A, B -> C, C -> A, C ->B 로 총 6개인것은 이해를 했습니다.
근데 최초의 물이 C에만 담겨있는데 왜
sender, receiver를 6크기의 배열로 선언해주고 아래처럼 for문을 돌리고 없는 물을 처음에 6개의 경로에 따라 퍼다 나르는지 이해가 잘 가지 않습니다.
for (int k = 0; k < 6; ++k)
{
// next[0] = a, next[1] = b, next[2] = c
int next[] = { a, b, c };
next[Receiver[k]] += next[Sender[k]];
next[Sender[k]] = 0;
// 대상 물통의 용량보다 물이 많아 넘칠 때
if (next[Receiver[k]] > now[Receiver[k]])
{
// 초과하는 만큼 다시 이전 물통에 넣음
next[Sender[k]] = next[Receiver[k]] - now[Receiver[k]];
// 대상 물통은 최대로 채움
next[Receiver[k]] = now[Receiver[k]];
}
// A와 B의 물의 양을 통하여 방문 배열 체크
if (visit[next[0]][next[1]] == false)
{
visit[next[0]][next[1]] = true;
q.push(make_pair(next[0], next[1]));
// A의 물의 양이 0일 때 C의 물의 용량을 정답 변수에 저장
if (next[0] == 0)
{
ret[next[2]] = true;
}
}
}
답변 2
0
0
2024. 01. 01. 16:47
안녕하세요. 반갑습니다 🙂
각 상태에서 물이 이동 가능한 경로인 6개를 모두 체크하기 위해 for문이 실행된다고 생각해주시면 좋을 것 같습니다. 해당 반목문은 최초 상태뿐 아니라 추후 진행되는 모든 상태마다 계속 체크가 됩니다.
최초 상태도 하나의 상태이기 때문에 따져보면
0 0 10 의 상태에서
A -> B, A ->C, B -> A, B -> C 이 4개의 상태는 A와 B의 물이 없기 때문에 실제로 무시가 됩니다.
(// A와 B의 물의 양을 통하여 방문 배열 체크
if (visit[next[0]][next[1]] == false)
실제로 해당 if문에서 걸러질 것입니다. )
C -> A, C ->B 만 실제로 물통 값의 변화를 일으키게 되고 여기에 따라
8 0 2, 0 9 1 의 중간 상태가 만들어 집니다.
그러면 이 각각의 상태에서도 또 해당 반복문을 통하여 각각 6개의 경로를 따져보게 됩니다.
이러한 방식으로 큐가 비어질 때 (더이상 탐색할 부분이 없을 경우)까지 진행하게 되고,
탐색한 데이터들 중 A의 값이 0일때의 C의 값들을 찾아 오름차순으로 정렬하여 주면
해당 문제를 해결 할 수 있습니다.
도움이 되셨으면 좋겠습니다.
새해복 많이 받으세요 :)