문제 풀이 질문드립니다.

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

작성한 질문수

자바 코딩테스트 - it 대기업 유제

7. "최소 회의실 개수" 문제 해법

작성

182

수정됨

혼자 풀다가 막힌 문제인데 어떻게 풀어야 할지 몰라서 질문드립니다.

문제를 간략하게 설명하면,

문제가 n*n행렬이 나오는데 (0,0)에서 사람이 움직이는데, 움직이는 조건이 왼손을 터치할 수 있는 방향으로만 움직일 수 있습니다. (0,0)에서 (n-1,n-1)로 나가는 경로의 길이를 구하라.

입니다.

만약 s에서 e로 간다면 답이 12가지 입니다.

s가 사람 모양이고 왼손을 터치할 수 있는 곳만 움직일 수 있습니다.

레벨탐색으로 하면서 큐를 잡는데

Queue<int[]> q = new LinkedList<>();

q.add(new int[] {x,y,1}); // x와y는 좌표, 1은 왼손을 터치할 수 있다는 표시로 풀려고 했는데 풀리지 않았습니다.

솔루션이 궁금합니다.

답변 1

안녕하세요 vkfksaosldk 님, 인프런 AI 인턴이에요.

문제를 분석해보니, 이는 그래프 탐색 알고리즘을 활용하여 해결할 수 있는 문제입니다. 하지만 문제에 제시된 조건인 왼손만을 이용하여 움직여야 한다는 점과 경로의 길이를 구해야 한다는 점 때문에 조금 더 복잡한 로직을 구현해야 합니다.

다음은 로직의 일부입니다.

주어진 행렬을 이용하여 그래프를 생성합니다.
BFS(Breadth-First Search)를 활용하여 시작점부터 탐색을 시작합니다.
큐에는 현재 위치와 왼손을 터치할 수 있는 횟수를 저장합니다.
현재 위치에서 이동 가능한 다음 위치들을 확인하고 큐에 넣습니다. 단, 단순 이동일 경우는 왼손을 터치할 수 있는 횟수가 변하지 않으며, 왼쪽으로 회전하는 경우 왼손을 터치한 횟수가 1 증가합니다.
도착점에 도달하면 현재까지 진행한 경로의 길이를 반환합니다.

이 로직을 구현하여 문제를 해결해보세요. 이 외에도 구체적인 코드나 추가적인 도움이 필요하다면 언제든지 물어보세요. 감사합니다!

작성한 질문수