인프런 커뮤니티 질문&답변

starkshn님의 프로필 이미지

작성한 질문수

Do it! 알고리즘 코딩테스트 with C++

그래프의 표현

백준 2251 C++ 질문 있습니다.

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

starkshn님의 프로필 이미지
starkshn
질문자

2024. 01. 01. 17:14

설명해주시니 이해가 좀 더 된거 같습니다.

바쁘실텐데 답변 해주셔서 감사합니다

새해복 많이 받으세요~~ :)

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의 값들을 찾아 오름차순으로 정렬하여 주면

해당 문제를 해결 할 수 있습니다.

 

도움이 되셨으면 좋겠습니다.

새해복 많이 받으세요 :)

starkshn님의 프로필 이미지

작성한 질문수

질문하기