[2021 카카오 채용연계형 인턴십] Q2. 거리두기 확인하기 (C++, Python, Java)

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/72410

 

예상 난이도

S5

 

알고리즘 분류

구현 or BFS/DFS

 

풀이

우선 단순 케이스 분류로 해결하는 풀이를 먼저 보겠습니다. 거리가 2 이하인 두 지점의 배치는 이렇게 3가지의 종류가 있습니다.

 

Case 1과 같은 배치가 나오면 바로 거리두기가 위배되었음을 확인 가능합니다.

 

Case 2와 같은 배치에서는 두 군데의 ? 지점이 모두 파티션인지 확인해야 합니다.

 

Case 3에서는 한 군데의 ? 지점이 파티션인지 확인해야 합니다.

 

각 응시자의 위치에 대해 Case 1, 2, 3번에 대응되는 위치들을 확인하면서 거리두기가 위배된 곳이 있는지 확인하면 됩니다. 여러 위치들을 하나하나 다뤄도 되지만 BFS/DFS에서 사용되는 방향 벡터를 이용하면 구현이 쉬워집니다. 자세한건 코드를 참고해주세요.

 

직접 구현을 하지는 않았지만, 각 응시자의 위치를 시작점으로 두고 BFS 혹은 DFS를 돌려 거리가 2 이내인 곳에 다른 응시자가 있는지 확인하는 풀이도 통과 가능합니다.

 

코드(C++)

#include <bits/stdc++.h>

using namespace std;

int dx1[4] = {1, 0, -1, 0};
int dy1[4] = {0, 1, 0, -1}; // 상하좌우

int dx2[4] = {1, -1, 1, -1};
int dy2[4] = {1, 1, -1, -1}; // 대각선

bool OOB(int x, int y){
    return x<0 || x>4 || y<0 || y>4;
}

int chk(vector<string>& board){
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            if(board[i][j] != 'P') continue;

            // 상하좌우로 거리가 1인 응시자 확인
            for(int dir = 0; dir < 4; dir++){
                int nx = i+dx1[dir];
                int ny = j+dy1[dir];
                if(!OOB(nx,ny) && board[nx][ny]=='P') return 0;
            }
            
            // 대각선에 위치한 응시자 확인
            for(int dir = 0; dir < 4; dir++){
                int nx = i+dx2[dir];
                int ny = j+dy2[dir];
                // 대각선에 응시자가 있을 경우 파티션 존재 여부 확인
                if(!OOB(nx,ny) && board[nx][ny]=='P'){
                    if(board[i][ny] != 'X' || board[nx][j] != 'X') return 0;
                }
            }
            
            // 상하좌우로 거리가 2인 응시자 확인
            for(int dir = 0; dir < 4; dir++){
                int nx = i+2*dx1[dir];
                int ny = j+2*dy1[dir];
                // 거리가 2인 곳에 응시자가 있을 경우 파티션 존재 여부 확인
                if(!OOB(nx,ny) && board[nx][ny]=='P'){
                    if(board[i+dx1[dir]][j+dy1[dir]] != 'X') return 0;
                }
            }
        }
    }
    return 1;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(auto& p : places) answer.push_back(chk(p));
    return answer;
}

 

코드(Python)

dx1 = [1,0,-1,0]
dy1 = [0,1,0,-1] # 상하좌우

dx2 = [1,-1,1,-1]
dy2 = [1,1,-1,-1] # 대각선

def chk(board):
    for i in range(5):
        for j in range(5):
            if board[i][j] != 'P': continue
            
            # 상하좌우로 거리가 1인 응시자 확인
            for dir in range(4):
                nx, ny = i+dx1[dir], j+dy1[dir]
                if 0 <= nx < 5 and 0 <= ny < 5 and board[nx][ny] == 'P':
                    return 0
            
            # 대각선에 위치한 응시자 확인
            for dir in range(4):
                nx, ny = i+dx2[dir], j+dy2[dir]
                # 대각선에 응시자가 있을 경우 파티션 존재 여부 확인
                if 0 <= nx < 5 and 0 <= ny < 5 and board[nx][ny] == 'P':
                    if board[i][ny] != 'X' or board[nx][j] != 'X':
                        return 0
            
            # 상하좌우로 거리가 2인 응시자 확인
            for dir in range(4):
                nx, ny = i+2*dx1[dir], j+2*dy1[dir]
                # 거리가 2인 곳에 응시자가 있을 경우 파티션 존재 여부 확인
                if 0 <= nx < 5 and 0 <= ny < 5 and board[nx][ny] == 'P':
                    if board[i+dx1[dir]][j+dy1[dir]] != 'X':
                        return 0
                
    return 1

def solution(places):    
    return [chk(place) for place in places]

 

코드(Java)

import java.util.*;

class Solution {
    static int dx1[] = {1, 0, -1, 0};
    static int dy1[] = {0, 1, 0, -1};

    static int dx2[] = {1, -1, 1, -1};
    static int dy2[] = {1, 1, -1, -1};

    public boolean OOB(int x, int y){
        return x<0 || x>4 || y<0 || y>4;
    }
    
    public int chk(String[] board){
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                if(board[i].charAt(j) != 'P') continue;
                
                // 상하좌우로 거리가 1인 응시자 확인
                for(int dir = 0; dir < 4; dir++){
                    int nx = i+dx1[dir];
                    int ny = j+dy1[dir];
                    if(!OOB(nx,ny) && board[nx].charAt(ny)=='P') return 0;
                }
                
                // 대각선에 위치한 응시자 확인
                for(int dir = 0; dir < 4; dir++){
                    int nx = i+dx2[dir];
                    int ny = j+dy2[dir];
                    if(!OOB(nx,ny) && board[nx].charAt(ny)=='P'){
                        if(board[i].charAt(ny) != 'X' || board[nx].charAt(j) != 'X') return 0;
                    }
                }
                
                // 상하좌우로 거리가 2인 응시자 확인
                for(int dir = 0; dir < 4; dir++){
                    int nx = i+2*dx1[dir];
                    int ny = j+2*dy1[dir];
                    // 거리가 2인 곳에 응시자가 있을 경우 파티션 존재 여부 확인
                    if(!OOB(nx,ny) && board[nx].charAt(ny)=='P'){
                        if(board[i+dx1[dir]].charAt(j+dy1[dir]) != 'X') return 0;
                    }
                }
            }
        }
        return 1;        
    }
    
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        for(int i = 0; i < 5; i++) answer[i] = chk(places[i]);
        return answer;
    }
}

 

관련 강의

0x09강 - BFS

0x0A강 - DFS

  Comments
댓글 쓰기