86번 피자배달거리

해결됨
DH 프로필

안녕하세요, 선생님

항상 좋은 강의 감사합니다.

1) 86번 질문

다름이 아니라 86번 문제에서 아무리 보아도 ch의 역할이 이해가 안갑니다.

DFS 함수 내부에 2중 포문으로 들어간

for (int j = 0; j < m; j++) {

int x2 = pz[ch[j]].first;

int y2 = pz[ch[j]].second;

이 부분이 특히 이해가 안갑니다..

int x2 = pz[j].first;

int y2 = pz[j].second;

 

가 아니라 ch[j] 가 필요한 이유가 무엇이죠,,?

체크 배열인건 알겠는데 무엇을 체크하기 위한 것인지 모르겠습니다.

어떤 것을 가리키는 인덱스 번호인지도요 ㅠㅠ

 

2) 그 외

현재 완강을 달려갑니다.

그런데도 새로운 DFS/BFS문제 및 다른 문제를 만나면 아예 풀지를 못하고 있습니다.

취업대비 코딩테스트 준비중인데 어떻게 해야할지 감이 안섭니다..코딩테스트까지는 2달 남았습니다.

시간상 하루 2문제씩 해당 강의 문제를 복습하고, 나머지 1문제는 새로운 문제를 푸는식으로 하루 3문제 정도 풀려고 하는데 괜찮은 계획인지 여쭤봅니다.

김태원 프로필
김태원 1달 전

문제에 있는 기본입력을 가지고 설명합니다.

4 4 

0 1 2 0 

1 0 2 1 

0 2 1 2 

2 0 1 2

각 피자집의 좌표가 pz 벡터 배열에 0번부터 차례대로 입력되어 있습니다.

ch 배열은 폐업되지 않고 살아남은 피자집의 pz배열 인덱스 번호를 저장하는 배열입니다.

ch배열의 값은 DFS가 돌면서 위에 그림처럼 변합니다. 

 

ch배열의 값이 변하는 과정을 아래 그림과 같습니다.

D(4, 3)이 호출되면 ch[cnt]=L이라는 코드를 하게 되며 이때 ch[3]=4가 되어 ch[3]값을 기존 3에서 4로 변경합니다. 그리고 D(5, 4)가 호출되어 if(cnt==m) 참이 되고 pz배열의 0, 1, 2, 4번 인덱스를 j for문이 접근하여 거리를 구하는 것입니다. 

D(4, 4), D(5, 4), D(6, 4) 처럼 두번째 매개변수가 4가 되어야 if(cnt==m) 이 참이되어 하나의 경우가 완성되는 것입니다.

D(7, 3), D(7, 4) 같은 경우는 if(L>pz.size()) return; 이 구문이 참이 되어 바로 종료해버립니다.

위 수형도를 이해하려고 노력해보세요.  이해가 잘 안되면 메일보내세요. 짧은 영상으로 설명해 드릴께요.

 

for (int j = 0; j < m; j++) {

      int x2 = pz[j].first;

     int y2 = pz[j].second;

위 코드처럼 해버리면 m값이 4이므로  j는 항상 0, 1, 2, 3으로만 변하기 때문에 pz배열의 0번, 1번, 2번, 3번에만 접근합니다. 즉 살아남은 피자집이 항상 (1, 3), (2, 3), (3, 2), (3, 4) 좌표에 있는 피자집만 되는 논리적 오류가 일어납니다.

 

▣ "새로운 DFS/BFS문제 및 다른 문제를 만나면 아예 풀지를 못하고 있습니다." 라고 하셨는데

어떤 문제를 풀다 못 푸셨는지 메일로 문제이름을 정확히 알려주시면 실력이 어느정도인지 알 수 있을 것 같습니다.

DH님의 실력을 알아야 정확한 조언을 해 줄 수 있을 것 같습니다.

김태원 프로필
김태원 1달 전

보충섹션에 86번 보충설명 영상 올려놓았습니다.