인프런 커뮤니티 질문&답변
작성한 질문수
8-X 강사님 코드 중 사소한 부분에 대한 질문이 있습니다.
작성
·
38
·
수정됨
0
안녕하세요.
강사님 해설 코드에서 중요한 부분은 아니지만 제 코드와 비교하는 과정에서 사소한 의문이 드는 부분이 있어 질문드립니다.
https://www.acmicpc.net/source/share/52caf2495c83482fb5912f0c5cbbf935
위 링크의 강사님 코드 중에서 60번째 줄의
int next_height = max(height[y][x], min(hole[y][x][i], height[ny][nx]));이 부분에서 next_height을 구하는 과정에서 height[ny][nx]을 넣을 필요가 없다고 생각됩니다.
코드 논리 상으로만 봤을 때 next_height가 hieght[ny][nx]값이 되게 되면 어차피 아래 if문
if(height[ny][nx] > next_height) 에서 걸러지기 때문에 어차피 next_height가 height[ny][nx]가 되는 게 유의미해지는 경우는 없습니다.
문제의 개념을 알고리즘으로 변환하는 과정에서도 설명해보자면, 우선순위큐에 우선 가장 바깥칸을 넣습니다. 맨 처음에 물탱크에 물을 가득 채운후에 가장 먼저 물이 빠져서 물높이가 낮아지는 칸들입니다. 이 칸들을 우선순쉬큐에 넣고 다익스트라 알고리즘으로 돌림으로써 물높이가 낮은 칸들의 인접한 칸에서 구멍을 통해 물이 흘러 들어오게 됩니다. (여기서 물높이가 낮은 칸 (우선순위큐에서 나오는 칸)은 흐름 상 더 높은 물높이를 갖는 칸입니다. 물론 물높이가 더 낮다면 고려할 필요가 없겠죠. 물 높이가 더 낮은 인접한 칸에서 물이 빠져나갈수는 없으니까요)
현재 탐색중인 칸에 인접한 물높이가 더 높은 칸에서 현재 물높이가 낮은 칸으로 물이 이동하는데 물높이가 낮은 칸은 결국 탐색해온대로 물높이가 더 낮은 칸 또는 바깥과 연결되어 물높이가 유지되고 인접한 칸은 물이 줄어드는 상황이 다익스트라 알고리즘이 반영된거라고 생각합니다.
그래서 큰돌님께서 강의에서 설명하신대로 (3:00 쯤 부분) 그림이 있을 때 바깥으로 물이 빠져 왼쪽에 물높이가 4, 오른쪽에 물높이가 1이고 구멍이 높이 3에 있을 때 양쪽 물의 높이가 3, 3으로 되는 것이 아니라 왼쪽 물이 높이가 3이 될 때까지 오른쪽으로 흘러가고 오른쪽은 물높이가 그대로 1이 유지되는 것이 자연스러운 설명이고 코드와 다익스트라 알고리즘에도 자연스럽게 설명이 되고 반영이 된다고 생각합니다.
이렇게 하면 위 코드를 문제 흐름 상 자연스레 아래처럼 표현이 가능하다고 보여집니다.
(코드 자체만으로 봤을 때도 그렇긴 하지만요.)
int next_height = max(height[y][x], height[ny][nx]);
큰돌님께서는 제 생각에 대해서 어떻게 생각하시는 지 피드백 부탁드립니다...!
항상 빠르고 좋은 답변 감사드립니다.
답변 1
0
안녕하세요 예찬님 ㅎㅎ
항상 예리한 질문 감사합니다.
if(height[ny][nx] > next_height) 에서 걸러지기 때문에 어차피 next_height가 height[ny][nx]가 되는 게 유의미해지는 경우는 없습니다.
-> 일단 저부분을 제거하고 제출했는데 통과가 되네요...
그러나 제 생각은 다음과 같습니다.
아래 예시를 들어 보겠습니다.
초기 물높이 h=10
칸 A(y,x)의 현재 물높이 height[y][x]=3(경계를 통해 “구멍 높이 3”으로 업데이트된 상태)
이웃 칸 B(ny,nx)의 현재 물높이 height[ny][nx]=10
A와 B를 잇는 구멍 높이 hole[y][x][i]=7
자, 여기서 다음의 코드의 경우, 정상적으로 7이 됩니다.
int next_height = max( height[y][x],
min(hole[y][x][i], height[ny][nx]) );
// = max( 3, min(7, 10) )
// = max( 3, 7 )
// = 7
if (height[ny][nx] > next_height) // 10 > 7 → true
height[ny][nx] = next_height; // B의 높이가 7로 떨어짐
이렇게 해야 경계에서 빠져나간 물높이 3 ->구멍 높이(7)를 넘어 B로 전파되어-> B가 7이 된다는 논리가 구현됩니다.
자 그러면 min을 제거해볼게요.
int next_height = max( height[y][x],height[ny][nx] );
// = max( 3, 10 )
// = 10
if (height[ny][nx] > next_height) // 10 > 10 → false
height[ny][nx] = next_height; // (절대 실행되지 않음)
B가 여전히 10을 유지해 버리기 때문에, 경계에서 빠져나간 물높이(3)가 “구멍 높이 7”을 타고 B로 전달되어야 하는 논리 자체가 없어지게 됩니다.
즉, 구멍의 높이와 이웃 칸의 현재 상한 중 더 낮은 쪽을 택해야만,“물은 구멍 높이를 넘어갈 수 없고, 이미 낮아진 옆 칸의 높이도 넘을 수 없다”는 문제의 핵심 개념이 코드에 정확히 반영되서 min(hole[y][x][i], height[ny][nx]) 부분은 빼면 안 될 것 같습니다.
참고가 될만한 그림을 그려봤습니다. (큰돌 손수메이드..)
다른 의견있으시면 언제든 말씀 부탁드립니다.
감사합니다.
아 죄송해요, 그 min(hole[y][x][i], height[ny][nx])에서 height[ny][nx]을 고려할 필요가 없어서 위의 코드처럼 해도 전혀 상관없다는 뜻이었습니다. 질문글에는 잘못적었네요. (height[ny][nx] -> hole[y][x][i]입니다..!)