구현

프로그래머스 2021 카카오 인턴 Level 2 문제 거리두기 확인하기를 Java를 이용하여 풀어보았다. 생각보다 로직 자체는 간단한데 내 코드는 좀 더럽다. 좀 더 간단하게 써볼 수 있을까 고민은 하지 않고 그냥 풀었다. ㅎ

문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/81302

---

맨해튼 거리 1,2인 움직임을 배열로 초기화

거리가 1,2 내에 파티션으로 막혀있지 않은 채로 두 사람 이상이 있으면 규칙 위반인 것이다. 그래서 거리가 1,2인 움직임을 모두 int[][] move로 초기화해주었다.

그리고 각각의 움직임별로 index를 매겨 특정 움직임을 index 번호를 통해 알 수 있도록 했다.

이를 코드로 구현한 건 다음과 같다.

static int[][] move = { {0,-2}, {-2,0}, {0,2}, {2,0}, {0,-1}, {-1,-1},
            {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1} }; // 맨해튼 거리가 1,2인 모든 움직임

그럼 이제 하나의 방 정보를 다 입력을 받고나서 그 방이 규칙을 준수하고 있는지 어떻게 확인하는가를 살펴보자.
나는 isDistanceAlright() 이란 메소드를 선언해서 방 하나씩을 판별하게 해주었다.

나의 solution 코드는 다음과 같다.

int[] solution(String[][] places) {
        int[] answer = new int[5];

        for(int room_num=0; room_num<5; room_num++){
            for(int row=0; row<5; row++){
                cur_room[row] = places[room_num][row].toCharArray(); // 방 정보 받기
            }
            answer[room_num] = isDistanceAlright();
        }

        return answer;
    }

cur_room의 정보에 따라서 규칙이 잘 지켜지고 있는지를 판단해주는 isDistanceAlright 메소드를 살펴보자.

static Integer isDistanceAlright(){
        boolean[][] visited = new boolean[5][5];

        for(int r=0; r<5; r++){
            for(int c=0; c<5; c++){
                if(cur_room[r][c]!='P') continue;

                for(int dir=0; dir<12; dir++){
                    int n_row = r + move[dir][0];   int n_col = c + move[dir][1];
                    if(!isInRagne(n_row,n_col)) continue; // 범위 밖이면 패스
                    if(cur_room[n_row][n_col]!='P') continue; // 사람 없으면 패스
                    if(visited[n_row][n_col])   continue;   // 이미 검사한 사람이면 패스
                    if(dir==4 || dir==6 || dir==8 || dir==10)   return 0; // 바로 옆에 사람 붙어있으면 규칙 위반

                    if(!isBlockedPath(r,c,dir)) return 0;
                }
                visited[r][c] = true;
            }
        }
        return 1;
    }

크게 어떤 로직을 따르고 있는지 살펴보자.

1. 5X5 방을 한 칸씩 살펴보며 사람이 들어있는 곳만 살펴보자.
2. 사람이 있는 곳이라면, 맨해튼 거리가 1~2인 곳을 모두 살펴보자. 앞서 미리 선언했던 move 배열을 통해 12방향을 다 살펴보자.
3. 12방향을 살펴볼 때는 다음 조건들을 만족하는 곳만 살펴볼 것이다.
(1) 5X5 범위 안에 있는곳
(2) 사람이 들어있는 곳
(3) 아직 방문하지 않은 사람이어야 함
4. 3의 세 가지 조건을 모두 만족한다면 다음으로 넘어가자.
(1) move[4], move[6], move[8], move[10]에 해당하는 곳에 사람이 있다면 그 말은 즉 사람끼리 나란히 붙어있다는 것이다. 따라서 바로 0을 반환한다.
(2) 그 외에는 isBlockedPath() 메소드를 통해 파티션을 사이에 두고 두 사람이 앉아있는지 확인해보자.

그렇다면 isBlockedPath() 메소드는 어떤 역할을 하는지 다음 코드를 보며 확인해보자.

static Boolean isBlockedPath(int r, int c, int dir){
        switch(dir){
            case 0:
                return (cur_room[r+move[4][0]][c+move[4][1]] == 'X');
            case 1:
                return (cur_room[r+move[6][0]][c+move[6][1]] == 'X');
            case 2:
                return (cur_room[r+move[8][0]][c+move[8][1]] == 'X');
            case 3:
                return (cur_room[r+move[10][0]][c+move[10][1]] == 'X');
            case 5:
                return ((cur_room[r+move[4][0]][c+move[4][1]] == 'X') && (cur_room[r+move[6][0]][c+move[6][1]] == 'X'));
            case 7:
                return ((cur_room[r+move[6][0]][c+move[6][1]] == 'X') && (cur_room[r+move[8][0]][c+move[8][1]] == 'X'));
            case 9:
                return ((cur_room[r+move[8][0]][c+move[8][1]] == 'X') && (cur_room[r+move[10][0]][c+move[10][1]] == 'X'));
            case 11:
                return ((cur_room[r+move[4][0]][c+move[4][1]] == 'X') && (cur_room[r+move[10][0]][c+move[10][1]] == 'X'));
        }
        return false;
    }

존나 정신없는 걸 볼 수 있다. 더 간단하게 쓰려면 쓸 수 있기는 한데... 굳이 필요성을 못 느꼈다. 너무 정신 없으니 부연 설명을 하겠다.

위에서 그림을 통해 확인했듯이 모든 움직임을 index 번호를 통해 표현할 수 있다. 예를 들어 위의 상황을 생각해본다면, (2,2)의 사람을 탐색 중인 경우를 가정해보자.

이 사람의 맨해튼 거리 1~2 내의 사람은 (2,0)과 (1,1) 두 명이다.

(2,0)과의 관계

두 사람 사이가 파티션으로 막혀있는지 알기 위해서는 단 한 칸의 정보만이 필요하다.
좌측으로 한 칸만 움직이는 move[4]의 움직임만 수행하고 그 칸이 X인지 확인하면 되는 것이다.

이를 코드로 표현하면 다음과 같다.

case 0: // move[0]의 움직임에 해당하는 칸이 사람인 경우
      return (cur_room[r+move[4][0]][c+move[4][1]] == 'X');

(1,1)과의 관계

대각선 방향의 관계에 있는 두 명은 두 칸을 확인해야 한다. 위 그림에서 확인할 수 있듯이 이때는 (2,1)과 (1,2)에 파티션이 있는지를 확인해서 두 칸 모두가 파티션이어야 BlockedPath 인 것이다.

이를 코드로 표현하면 다음과 같다.

case 5: // move[5] 의 움직임에 해당하는 칸이 사람인 경우
      return ((cur_room[r+move[4][0]][c+move[4][1]] == 'X') && (cur_room[r+move[6][0]][c+move[6][1]] == 'X')); // 두 칸을 모두 파티션으로 막아줘야 한다.

이런 식으로 4,6,8,10과 같이 나란히 붙어있는 칸을 제외한 0,1,2,3,5,7,9,11 의 움직임을 모두 확인해주기 위한 isBlockedPath 메소드의 전체 코드를 살펴보면 다음과 같이 개떡같이 되는 것이다.

static Boolean isBlockedPath(int r, int c, int dir){
        switch(dir){
            case 0:
                return (cur_room[r+move[4][0]][c+move[4][1]] == 'X');
            case 1:
                return (cur_room[r+move[6][0]][c+move[6][1]] == 'X');
            case 2:
                return (cur_room[r+move[8][0]][c+move[8][1]] == 'X');
            case 3:
                return (cur_room[r+move[10][0]][c+move[10][1]] == 'X');
            case 5:
                return ((cur_room[r+move[4][0]][c+move[4][1]] == 'X') && (cur_room[r+move[6][0]][c+move[6][1]] == 'X'));
            case 7:
                return ((cur_room[r+move[6][0]][c+move[6][1]] == 'X') && (cur_room[r+move[8][0]][c+move[8][1]] == 'X'));
            case 9:
                return ((cur_room[r+move[8][0]][c+move[8][1]] == 'X') && (cur_room[r+move[10][0]][c+move[10][1]] == 'X'));
            case 11:
                return ((cur_room[r+move[4][0]][c+move[4][1]] == 'X') && (cur_room[r+move[10][0]][c+move[10][1]] == 'X'));
        }
        return false;
    }

너무 괴기스럽게 생겼지만 사실 로직 자체는 매우 단순하다. 예쁘게 쓰려고 하면 오히려 고도의 압축을 하기 위해 불필요한 영역에 머리를 쓰느라 시간만 더 걸리는 것 같다. 좀 단순 무식해도 단순 무식하게 금방 풀리는 문제라면 그냥 이렇게 푸는 게 나은 것 같다는 생각도 든다.

다음은 위의 모든 코드를 다 합쳐 내가 제출한 코드다.

import java.io.*;

public class SocialDistance {
    static char[][] cur_room = new char[5][5]; // 방 하나 정보 받을 배열
    static int[][] move = { {0,-2}, {-2,0}, {0,2}, {2,0}, {0,-1}, {-1,-1},
            {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1} }; // 맨해튼 거리가 1,2인 모든 움직임

    static int[] solution(String[][] places) {
        int[] answer = new int[5];

        for(int room_num=0; room_num<5; room_num++){
            for(int row=0; row<5; row++){
                cur_room[row] = places[room_num][row].toCharArray(); // 방 정보 받기
            }
            answer[room_num] = isDistanceAlright();
        }

        return answer;
    }

    static Integer isDistanceAlright(){
        boolean[][] visited = new boolean[5][5];

        for(int r=0; r<5; r++){
            for(int c=0; c<5; c++){
                if(cur_room[r][c]!='P') continue;

                for(int dir=0; dir<12; dir++){
                    int n_row = r + move[dir][0];   int n_col = c + move[dir][1];
                    if(!isInRagne(n_row,n_col)) continue; // 범위 밖이면 패스
                    if(cur_room[n_row][n_col]!='P') continue; // 사람 없으면 패스
                    if(visited[n_row][n_col])   continue;   // 이미 검사한 사람이면 패스
                    if(dir==4 || dir==6 || dir==8 || dir==10)   return 0; // 바로 옆에 사람 붙어있으면 규칙 위반

                    if(!isBlockedPath(r,c,dir)) return 0;
                }
                visited[r][c] = true;
            }
        }
        return 1;
    }

    static Boolean isBlockedPath(int r, int c, int dir){
        switch(dir){
            case 0:
                return (cur_room[r+move[4][0]][c+move[4][1]] == 'X');
            case 1:
                return (cur_room[r+move[6][0]][c+move[6][1]] == 'X');
            case 2:
                return (cur_room[r+move[8][0]][c+move[8][1]] == 'X');
            case 3:
                return (cur_room[r+move[10][0]][c+move[10][1]] == 'X');
            case 5:
                return ((cur_room[r+move[4][0]][c+move[4][1]] == 'X') && (cur_room[r+move[6][0]][c+move[6][1]] == 'X'));
            case 7:
                return ((cur_room[r+move[6][0]][c+move[6][1]] == 'X') && (cur_room[r+move[8][0]][c+move[8][1]] == 'X'));
            case 9:
                return ((cur_room[r+move[8][0]][c+move[8][1]] == 'X') && (cur_room[r+move[10][0]][c+move[10][1]] == 'X'));
            case 11:
                return ((cur_room[r+move[4][0]][c+move[4][1]] == 'X') && (cur_room[r+move[10][0]][c+move[10][1]] == 'X'));
        }
        return false;
    }

    static Boolean isInRagne(int row, int col){
        if(row<0 || row>=5 || col<0 || col>=5)  return false;
        return true;
    }

    public static void main(String args[]) throws IOException {
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[][] places = { {"POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"},
                                {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"},
                                {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"},
                                {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"},
                                {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"} };
        int[] answer = solution(places);
        for(int i: answer)
            bfw.write(i + " ");
        bfw.close();
    }
}

오늘 배운 것

무식하게 풀어도 쉽게 풀리면 무식하게 풀자.