3-C 강의 내용 질문
281
작성한 질문수 22
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;
}0
2중 for문 안쪽에서 수정한다는 점에서 바로바로 수정한다고 느꼈던 것 같습니다! 한 턴당 여러 번의 dfs를 하기 때문에 앞선 dfs에서 수정했던 부분에 다시 접근하지 않을까 생각했습니다.
답변 보고 예제를 다시 돌려봤는데 visited 체크 하는 부분 때문에 다시 이동이 일어나지 않네요. 답변 감사합니다!!
0
이 답변이 도움이 되었습니다~
(다른 학습자 분을 위해 제 의식의 흐름을 남겨놓습니다)
문제를 풀다보면
"위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다." 조건을 보고
dfs 로 연합 국가 그룹을 모두 찾고나서, 인구 이동을 시행해야할 것만 같다는 생각을 하게 되었는데
(왜냐하면, 연합 그룹이 2개 이상 생길 수 있는 경우, 한 그룹에서 먼저 인구이동을 하면, 다음 그룹의 dfs 시 인접 국가의 인구 수가 달라져 영향을 줄 것이라고 생각해서)
어차피, visited 배열을 통해 이미 탐색한 국가는, 다음 탐색 때 제외되기 때문에 연합 그룹을 찾는 즉시 인구 이동을 시행해도 무방한 것이라는 걸 깨달았습니다.
1-E질문입니다!
0
533
2
3-L 틀린 부분 피드백 부탁드립니다.
0
835
2
1-A문제 순열재귀함수 질문입니다.
0
396
1
1-A 일곱난쟁이문제입니다
0
469
1
문제 풀 때 방향성에 대해
0
809
1
맥에서 vs code로 실행 관련 질문입니다
0
530
1
17071번 메모리 초과
0
389
1
1-C질문입니다!
0
428
2
2-B BFS 시간초과질문
0
637
2
1-O 13번 라인
0
445
1
6-J 놀이공원 문제 질문
0
388
1
구현관련 질문
0
491
1
강의 교안
0
321
1
실력을 더 올리고나서 강의를 보는 것이 맞을까요?
0
550
1
안녕하세요! 재귀함수에 관해서 질문드립니다
0
539
1
1-K
0
481
2
3-G번 질문있습니다.
1
480
3
3-C 실행 시간 질문드립니다.
0
502
1
4-A 문제 풀이 질문있습니다.
0
601
2
비트마스킹 연산자 "1의 보수" 영문 표기법
0
441
1
격자탐색 문제에서 BFS 시간복잡도 질문드립니다.
0
349
1
3-O go 함수 질문 드립니다.
1
452
2
4-A 출력 질문
0
307
1
1주차 1-O 질문드립니다
0
264
1