4-H 질문드려요

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

4-H

해결된 질문

작성

안녕하세요 큰돌님. 혼자 문제 풀어보고 있는데 일단 방법이 생각나지 않아 전부 탐색하는 방향으로 해보았습니다. 일단 메모리 초과 오류가 났습니다.

그런데 제가 코드에서

ans1 = 1;

이라고 지정하고 뒤에서 -1을 해주는데. 이걸 없이 시작하면 무한루프에 걸리는거같습니다. 제 컴퓨터가 이상한걸까요 ? 코드가 이상한걸까요 ? http://boj.kr/6f2fe3545c524355844338f8f9cc1a83

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 정재님ㅎㅎ

int dfs(int y, int x, int idx) {
	
	queue<pair<int, int>> q;
	q.push({ y, x });
	visited[y][x] = idx;

이부분 때문에 그렇습니다. 만약에 ans1을 0으로만 해놓으면 idx에는 0이 되서 방문처리가 계속안돼 -> 정점을 계속해서 다시방문 -> 계속되는 무한루프가 발생하고 맙니다.

이 때문에 ans1에는 0 이외의 값 -> dfs 매개변수 idx로 할당

이런 구조를 가져야 합니다.

1로 하는게 좋습니다.


				if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
				ans3 = max(ans3, v[visited[i][j]] + v[visited[ny][nx]]);

그리고 이부분. 서로 다른 방일 경우 -> 합쳐야 하는데 해당 로직이 없습니다.

이부분만 다시 해보시겠어요?

감사합니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. 이정재님, 질문해 주셔서 감사합니다.

질문 내용을 보니 ‘메모리 초과’와 ‘무한루프’ 두 가지 문제가 발생하고 있어 고민하시는 것 같습니다. 각각의 문제를 살펴보겠습니다.

메모리 초과 오류:
- 메모리 초과는 프로그램이 할당된 메모리 이상을 사용할 때 발생합니다. 전부 탐색을 구하는 경우는 특히 수가 많아지면 그러한 문제가 발생하기 쉽습니다. 사용하신 데이터 구조나 배열이 너무 크지는 않은지 확인해 보세요. 또한, 동적 메모리 할당을 과도하게 사용하고 있다면 이를 점검해보세요.
무한루프 문제:
- 기본적으로 루프가 끝나는 조건이 크거나 작아서 무한 반복될 경우가 있습니다. 예를 들면, 반복문 안에서 루프 변수를 변경하지 않거나, 종료 조건이 부적절한 경우가 있습니다.
- ans1 = 1;로 설정한 후 -1을 하는 부분에서 그 변수가 반복문 안에서 어떻게 변하는지, 그리고 조건에 적절히 사용되고 있는지 확인해야 합니다.

관련된 질문 게시물을 통해 비슷한 사례를 확인하며 방향을 잡아볼 수 있습니다:
- 4-C 질문에서는 세그멘테이션 폴트와 관련된 코드 설명이 있습니다. 코드상의 특정 부분이 문제를 복잡하게 만들거나 예기치 않은 값을 참조할 수 있음을 이해하는 데 도움이 될 것입니다.

메모리와 관련된 최적화, 무한루프를 방지하기 위한 조건 설정 방법 등을 통해 코드를 개선하시면 문제 해결에 도움이 될 것입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

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

4-H 질문드려요