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

안녕하세요 ㅎㅎ

	visited[0][n] = 1;
	q.push(n);

	if (n == k)
	{
		cout << 0 << "\n";
		return 0;
	}

	while (q.size())
	{
		k += trun;
		if (k > MAX) break;
		if (visited[trun % 2][k])
		{
			ok = true;
			break;
		}

		int size = q.size();
		for (int i = 0; i < size; ++i)
		{
			int now = q.front();
			q.pop();

			for (int next : {now + 1, now - 1, now * 2})
			{
				if (next <0 || next >MAX) continue;
				if (visited[(trun+1) % 2][next]) continue;

이렇게 하게 되면 의미자체가 틀린 코드가 됩니다.

저 for문안에서 하고자 하는 것은 지금의 trun에서 next라는 정점을 갔을 때의 방문을 확인하는 코드인데요.

저기서 + 1을 기반으로 하게 되면 해당 의미가 깨져서 틀리게 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요 mch님ㅎㅎ

오랜만이네요.

저렇게 할경우에는 turn에 따른 부분을 좀 조정해주어야 할 것 같은데요. 전체 코드 부탁드립니다.

감사합니다.

안녕하세요, 인프런 AI 인턴입니다.
mch473700님께서 문의 주신 코드에 대한 이해를 돕기 위해 추가 설명을 드리겠습니다.

님께서 질문하신 코드 로직에서 사용하는 visited 배열의 인덱스 접근 방식 차이로 인해 결과가 다르게 나오는 것 같습니다.
구체적으로 살펴보면:

1. 코드 차이점

   • 님의 방법:

     if (visited[(turn+1) % 2][next]) continue;
     visited[(turn+1) % 2][next] = visited[(turn) % 2][now] + 1;
     

     이 방법은 다음 턴의 상태를 방문했는지 체크하고, 방문 기록을 갱신하려고 시도합니다. 이는 논리적인 오류를 발생시킬 수 있습니다.

   • 선생님의 방법:

     if (visited[(turn) % 2][next]) continue;
     visited[(turn) % 2][next] = visited[(turn +1) % 2][now] + 1;
     

     이 방법은 현재 턴의 상태를 적절하게 비교하고, 앞선 턴의 값을 기반으로 방문 기록을 갱신합니다.

2. 논리적 차이

   • BFS와 같은 탐색 알고리즘에서 visited 배열은 전 방한 여부를 추적하고, 그 안에 저장되는 값이 다음 상태로의 이동에 필요한 비용이나 경과 시간을 나타낼 수 있습니다.
     
   • 선생님의 방법은 “현재 턴”과 “직전 턴” 정보를 올바르게 활용하여 이동 경로를 추적 및 계산하여 정확한 결과를 내는 것으로 보입니다.
     

가능하면 기존 답변을 다음 게시글에서 확인해 보시길 권장드립니다:

• 3-I, 결과값에 대한 질문입니다
  
• 17071번 메모리 초과
  

두 코드를 비교하며 각각의 인덱싱 방식이 어떻게 문제를 해결하는지를 분석하시면 이해에 도움이 될 것입니다.

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