카테고리: 배열

문제

https://school.programmers.co.kr/learn/courses/30/lessons/81302

풀이 방식

맨해튼 거리가 2 이하인 경우를 확인하는 방법은, 어떤 P가 상하좌우 방향으로 총 2번 이동했을때 다른 P를 만나는 경우 입니다. 한번 이동했을 때 바로 P를 만난다면 거리두기를 지키지 않은 경우로 검사를 종료하고, O를 만나면 한번 더 이동이 가능므로 검사를 한번 더 진행합니다.

정리하면 다음과 같은 흐름을 가지게 됩니다.

1. 대기실의 모든 응시자에 대해 검사
   1-1. 상하좌우 방향 중 빈 테이블이 있다면 해당 자리로 이동 후 1-2를 재진행
   1-2. 상하좌우 방향 중 응시자를 만난다면 거리두기를 지키지 않아 검사 종료
2. 모든 응시자에 대한 검사를 통과하면 거리두기를 잘 지킨 것

1. dx, dy 정의

// 상 하 좌 우 
private static int[] dx = {0, 0, -1, 1};
private static int[] dy = {-1, 1, 0, 0};

2. 5x5 대기실 만들기

for(int i = 0; i < places.length; i ++){
    char[][] place = new char[5][5];
    for(int j = 0; j < 5; j++){
    	place[j] = places[i][j].toCharArray();
    }

	// 대기실 별로 확인
    ...
}

3. 대기실의 모든 응시자 확인

 private boolean isDistanced(char[][] place){
 	for(int y = 0; y < 5; y++){
    	for(int x = 0; x < 5; x++){
        	// 응시자가 앉아있을때만 거리두기 검사
            if(place[y][x] == 'P'){
            	//상하좌우 방향 조사
                ...
            }
        }
    }	

	return true;
}

4. 응시자의 상하좌우 방향 검사

private boolean move(char[][] place, int x, int y){
	for(int d = 0; d < 4; d++){
    	int next_x = x + dx[d];
        int next_y = y + dy[d];
        if(next_x == -1 || next_x == 5 || next_y == -1 || next_y == 5) continue;

			//P를 만났다. 검사 종료
            if(place[next_y][next_x] == 'P') return false;
            
            //빈테이블(O)을 만났다. 재검사 필요
            if(place[next_y][next_x] == 'O'){
            	//이동했던 방향을 제외한 나머지 방향에 P가 있는지 확인
                   ...
            }
            //X를 만났다. 별도 검사 필요 없음.
    }

	return true;
}

4. 빈 테이블 발견 시, 상하좌우 한번 더 검사 (그 전 검사 방향의 반대방향은 제외하고 검사해야함)

private boolean move(char[][] place, int x, int y, int exclude){
	switch (exclude) {
    	case 0 :
        	exclude = 1;
            break;
        case 1 :
        	exclude = 0;
            break;
        case 2 :
        	exclude = 3;
            break;
        case 3 : exclude = 2;
   	}

	for(int d = 0; d < 4; d++){
    	if( d == exclude ) continue;
        int next_x = x + dx[d];
        int next_y = y + dy[d];
        if(next_x == -1 || next_x == 5 || next_y == -1 || next_y == 5) continue;

		//P를 만났다.
        if(place[next_y][next_x] == 'P') return false;
    }

	return true;
}

최종 코드

class Solution {
    private static int[] dx = {0, 0, -1, 1};
    private static int[] dy = {-1, 1, 0, 0};

    private boolean move(char[][] place, int x, int y, int exclude){
        switch (exclude) {
            case 0 :
                exclude = 1;
                break;
            case 1 :
                exclude = 0;
                break;
            case 2 :
                exclude = 3;
                break;
            case 3 : exclude = 2;
        }

        for(int d = 0; d < 4; d++){
            if( d == exclude ) continue;
            int next_x = x + dx[d];
            int next_y = y + dy[d];
            if(next_x == -1 || next_x == 5 || next_y == -1 || next_y == 5) continue;

            //P를 만났다.
            if(place[next_y][next_x] == 'P') return false;
        }

        return true;
    }

    private boolean move(char[][] place, int x, int y){
        for(int d = 0; d < 4; d++){
            int next_x = x + dx[d];
            int next_y = y + dy[d];
            if(next_x == -1 || next_x == 5 || next_y == -1 || next_y == 5) continue;

            //P를 만났다.
            if(place[next_y][next_x] == 'P') return false;
            //O를 만났다
            if(place[next_y][next_x] == 'O'){
                //이동했던 방향을 제외한 나머지 방향에 P가 있는지 확인
                if(!move(place, next_x, next_y, d)) return false;
            }
            //X를 만났다.
        }

        return true;
    }

    private boolean isDistanced(char[][] place){
        for(int y = 0; y < 5; y++){
            for(int x = 0; x < 5; x++){
                // 응시자가 앉아있을떄만 거리두기 검사
                if(place[y][x] == 'P'){
                    //현재 위치:place[y][x]
                    if(!move(place, x, y)) return false;
                }
            }
        }

        return true;
    }



    public int[] solution(String[][] places) {

        // 어떤 P가 상하좌우 방향으로 2번 이동해서 다른 P를 만나면 거리두기를 지키지 않은 것
        // O를 만나면 이동 가능, X를 만나면 이동할 수 없음
        // 배열에 있는 모든 P를 움직여봐야함

        int[] result = new int[places.length];

        for(int i = 0; i < places.length; i ++){
            // 대기실 만들기
            char[][] place = new char[5][5];
            for(int j = 0; j < 5; j++){
                place[j] = places[i][j].toCharArray();
            }

            // 대기실 별로 확인
            if(isDistanced(place)){
                result[i] = 1;
            }else{
                result[i] = 0;
            }
        }

        return result;
    }
}