인프런 커뮤니티 질문&답변
작성한 질문수
3-C 강의 내용 질문
작성
·
276
0
http://boj.kr/ed64f619d6c14451b5d858f2b1f4c3ba
강의 내용 관련 질문이지만 질문 규칙에 따라서 제 코드도 첨부합니다. 저 코드는 배열을 바로바로 수정하지 않고 v1, v2 배열에 모아 두었다가 모든 DFS가 끝나면 한 번에 배열을 수정하는 코드입니다.
강의에서는 연합을 하나 찾을 때마다 바로 배열 A를 수정하고 있습니다.
이 경우 같은 턴에서 다른 연합을 찾을 때 배열을 수정한 게 영향을 미칠 것 같은데 그러지 않는 이유가 궁금합니다.
예를 들어 테스트 4에서
3 5 10
10 15 20
20 30 25
40 22 10
(0, 0)에서 DFS를 한 후 배열을 수정하면 아래의 배열이 되는데
20 20 20
20 20 20
40 20 10
변경된 상태에서는 같은 턴에서 (2, 2)를 기준으로
(2, 1), (1, 2)와 연합을 형성할 수 있기 때문에
최종 상태는 아래와 같아질 것이라고 생각했습니다.
20 20 20
20 20 16
40 16 16
답변 1
2
안녕하세요 yeon님 ㅎㅎ 열심히 하시네요
근데 저 바로바로 수정하지 않고 아래코드처럼 이렇게 수정하는데 혹시 어떤 부분이 바로 수정한다고 느끼시는 건가요?
아 또한, dfs로 visited로 확인해놔서 방문한 정점은 다시 방문하지 않기 때문에 한 턴에 한 부분이 다시 이동이 일어날 일은 없습니다.
for(pair<int,int> b : v){
a[b.first][b.second] = sum / v.size();
flag = 1;
}
이 답변이 도움이 되었습니다~
(다른 학습자 분을 위해 제 의식의 흐름을 남겨놓습니다)
문제를 풀다보면
"위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다." 조건을 보고
dfs 로 연합 국가 그룹을 모두 찾고나서, 인구 이동을 시행해야할 것만 같다는 생각을 하게 되었는데
(왜냐하면, 연합 그룹이 2개 이상 생길 수 있는 경우, 한 그룹에서 먼저 인구이동을 하면, 다음 그룹의 dfs 시 인접 국가의 인구 수가 달라져 영향을 줄 것이라고 생각해서)
어차피, visited 배열을 통해 이미 탐색한 국가는, 다음 탐색 때 제외되기 때문에 연합 그룹을 찾는 즉시 인구 이동을 시행해도 무방한 것이라는 걸 깨달았습니다.
2중 for문 안쪽에서 수정한다는 점에서 바로바로 수정한다고 느꼈던 것 같습니다! 한 턴당 여러 번의 dfs를 하기 때문에 앞선 dfs에서 수정했던 부분에 다시 접근하지 않을까 생각했습니다.
답변 보고 예제를 다시 돌려봤는데 visited 체크 하는 부분 때문에 다시 이동이 일어나지 않네요. 답변 감사합니다!!