[Programmers] 블록 이동하기

문제

 

2020 KAKAO BLIND RECRUITMENT > 블록 이동하기

코딩테스트 연습 - 블록 이동하기

 

 

아이디어

 

이번 문제는 평범한 BFS로 길 찾는 문제들의 심화 버전이라고 생각합니다.

 

로봇이 차지하는 공간이 2칸이어도 사방탐색을 하는 데는 어려움이 없었지만 회전하는 경우를 구할 때 말썽을 많이 부렸습니다.

 

초기 코드가 구현되었을 때는 회전하는 부분이 복잡하고 길었지만 구현하고 나서 생각을 다시 정리해보니 회전하는 경우를 판단할 때 매우 간단한 코드로 변경할 수 있었습니다.

 

생각한 방법에 대해 간단하게 설명드리겠습니다.

 

로봇이 가로 방향으로 배치되어 있다면 다음과 같이 회전되는 케이스가 생깁니다.

 

회전되는 경우

 

 

그리고 사방 탐색을 할 때 북쪽 방향으로 움직일 수 있다면 가로 방향일 때만 (i1, j1, nexti1, j1), (i2, j2, nexti2, j2)의 값으로 회전되는 케이스를 구할 수 있었습니다.

 

남쪽 방향으로 움직일 수 있을 때도 북쪽 방향일때와 동일하게 (i1, j1 ,nexti1, j1), (i2, j2, nexti2, j2) 값이 회전되는 케이스가 나오게 됩니다.

 

동일한 방식으로 세로 방향일 때는 서쪽과 동쪽 방향으로 움직일 때 회전되는 케이스를 구할 수 있었습니다.

 

 

구현 코드 (Java)

 

import java.util.*;

class Solution {
    public int solution(int[][] board) {
    	int dirj[] = {1, 0, -1, 0};
    	int diri[] = {0, 1, 0, -1};
        int n = board.length;
        boolean visited[][][][] = new boolean[n][n][n][n]; // 방문 여부 체크 [로봇 한쪽의 i][로봇 한쪽의 j][로봇 다른 한쪽의 i][로복 다른 한쪽의 j]
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(new Node(0, 0, 0, 1, 0));
        int res = 0;
        
        while(!queue.isEmpty()) {
        	Node node = queue.poll();
        	
        	if(node.i1 == n-1 && node.j1 == n-1) { // 목적지 도착 확인
        		res = node.count;
        		break;
        	}
        	
        	if(node.i2 == n-1 && node.j2 == n-1) { // 목적지 도착 확인
        		res = node.count;
        		break;
        	}
        	
        	if(visited[node.i1][node.j1][node.i2][node.j2]) { // 방문여부 체크
        		continue;
        	}
        	
        	visited[node.i1][node.j1][node.i2][node.j2] = visited[node.i2][node.j2][node.i1][node.j1] = true;
        	
        	for(int a=0; a<4; a++) { // 사방탐색
        		int nexti1 = node.i1 + diri[a];
        		int nextj1 = node.j1 + dirj[a];
        		int nexti2 = node.i2 + diri[a];
        		int nextj2 = node.j2 + dirj[a];
        		
        		if(nexti1 >= n || nexti1 < 0 || nextj1 >= n || nextj1 < 0 || nexti2 >= n || nexti2 < 0 || nextj2 >= n || nextj2 < 0 || 
        				visited[nexti1][nextj1][nexti2][nextj2] || visited[nexti2][nextj2][nexti1][nextj1] || 
        				board[nexti1][nextj1] == 1 || board[nexti2][nextj2] == 1) {
        			continue;
        		}
        		
        		queue.add(new Node(nexti1, nextj1, nexti2, nextj2, node.count+1));
        		
        		if(node.i1 == node.i2 && a%2 == 1) { // 로봇이 가로인 상태에서 a방향으로 회전할 경우
        			queue.add(new Node(node.i1, node.j1, nexti1, node.j1, node.count+1));
        			queue.add(new Node(node.i2, node.j2, nexti2, node.j2, node.count+1));
        		}
        		
        		if(node.j1 == node.j2 && a%2 == 0) { // 로봇이 세로인 상태에서 a방향으로 회전할 경우
        			queue.add(new Node(node.i1, node.j1, node.i1, nextj1, node.count+1));
        			queue.add(new Node(node.i2, node.j2, node.i2, nextj2, node.count+1));
        		}
        	}
        }
        
        return res;
    }
    
    private static class Node {
    	int i1, j1, i2, j2, count; // 로봇의 좌표값, 움직인 횟수

		public Node(int i1, int j1, int i2, int j2, int count) {
			this.i1 = i1;
			this.j1 = j1;
			this.i2 = i2;
			this.j2 = j2;
			this.count = count;
		}
    }
}

 

 

읽어주셔서 감사합니다.