-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
5-M 질문
24.03.01 14:43 작성 24.03.01 14:44 수정 조회수 88
0
안녕하세요 큰돌님!
회전에 대한 아이디어를 떠올리지 못해서
4방향에 대해서 dfs 돌리면서 구현해 보았는데
TC는 다 통과하는데 바로 틀렸다고 나와서 질문 드립니다 ㅠㅠ 어느 부분을 신경쓰지 못한 걸까요?
일단 저는 3가지 pair<int,int>형 배열을 사용하고
3가지 함수를 구현 했습니다.
우선 3가지 pair<int,int> 배열입니다.
pair<int, int> startPos[4] = { {0,0},{20,0},{0,0},{0,20} }; // 위,아래,왼,오 부터 시작할때의 시작 위치
pair<int, int> NextRow[4] = { {0,1},{0,1},{1,0},{1,0} }; // 각 방향에 대해서 다음 줄로 이동하기 위한 pos 양. ex) 위일 경우 한줄하고 다음 열로 가서 해야함
pair<int, int> NextPos[4] = { {1,0}, {-1,0},{0,1},{-1,0} }; // 한 줄에 대해서 다음 Pos로 가기 위한 이동 양. ex) 위일 경우 0번행부터(열고정) 끝 행까지 검사해야 한다.3가지 함수 프로토 타입입니다.
void dfs(int cnt, int curIdx);
void moving(int dirIdx, int PivotIdx, int InputIdx);
void updataMaxRet(int findIdx);dfs : 최대 5번까지의 이동을 하기 위함. dfs에 들어가면 4방향에 대해서 이동한다.
dfs에서 각 방향에 대해서 호출되는 함수로. 새로운 배열에 이동된 값들을 넣어준다.
이동된 새로운 배열에 대해서 최대값 업데이트
코드 링크는 여기있습니다.
답변을 작성해보세요.
0
큰돌
지식공유자2024.03.04
안녕하세요 성은님 ㅎㅎ
잘 짜셨지만 이 같은 반례를 해결하지 못하는 것 같습니다.
반례는 다음과 같습니다.
반례
10 0 0 64 32 32 0 0 0 0 0 0 32 32 64 0 0 0 0 0 0 0 0 128 0 0 0 0 0 0 0 64 64 128 0 0 0 0 0 0 0 0 0 64 32 32 0 0 0 0 0 0 32 32 64 0 0 0 0 0 0 0 0 128 0 0 0 0 0 0 0 64 64 128 0 0 0 0 0 0 0 128 32 0 0 0 0 0 0 0 0 0 0 128 0 0 0 0 0 0 0
정답 : 1024
성은님 코드 : 512
감사합니다.
0
인프런 AI 인턴
2024.03.03
안녕하세요, 인프런 AI 인턴입니다.
크돌님, 회전 문제를 해결하기 위한 dfs 구현 관련해서 맞닥뜨리신 어려움에 대해 질문 주셨네요.
귀하께서 제공하신 코드 분석을 통해 회전 로직이나 DFS 구현에서 발생한 문제점을 파악하는 것이 중요한데요,운fortunuately, 저는 직접적으로 코드를 실행하진 않지만, 코드 설계 방향성에 대한 피드백은 드릴 수 있습니다.
회전이 제대로 수행되었는지 확인하기 위해 각 단계에서 상태 변화를 출력해볼 수 있습니다. 이를 통해 각 단계별로 예상한대로 함수가 수행 되고있는지 확인해 보세요.
moving 함수 내에서 배열의 인덱스가 유효한 범위 내에 있는지, 배열의 경계 조건을 벗어나지 않았는지 확인해 보는 것이 중요합니다.
최대값 업데이트를 진행하는 updataMaxRet 함수에서 현재 상태의 점수가 정확히 계산되었는지, 필요하다면 디버깅을 통해 잘못된 점이 없는지 검토해 보세요.
DFS 탐색 시 중복 탐색을 방지하고 효율적인 방문 처리가 이루어지고 있는지 확인해야 할 수 있습니다.
다른 가능성으로는 방향을 정하는 로직에 오류가 없는지, 즉 startPos, NextRow, NextPos 배열이 올바르게 설정되었는지 검토해 보세요.
경우에 따라, 특정 문제 상황에서 edge case를 놓치실 수도 있으니, 모든 가능성을 고려해서 코드를 검토하는 것이 중요합니다.
위의 사항들을 차근차근 점검해 나가면서 문제를 해결하시길 바랍니다. 계속해서 도전하시고 고민하는 과정에서 좋은 결과가 나오기를 응원합니다!
답변 2