거리두기 확인하기(카카오) 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

대기실에서 모든 사람들이 거리두기를 지키고 있는지 여부를 구하는 문제이며, 거리 두기의 경우 맨하튼 거리가 2이하인 부분에 대해, 서로가 파티션으로 구분되어야만 한다. 대기실에서 각 사람마다 주변 맨하튼 거리가 2이내를 확인하여 거리두기가 지켜지는지 여부를 확인하고, 한 명이라도 지키지 않았다면 0을 반환하도록 한다.

 

핵심부분은 특정 사람에 대해 주변 맨하튼 거리가 2이내인 부분을 확인하는 부분이며 처리과정을 아래와 같다.

1. 상,하,좌,우를 확인한다
    1.1. 거리가 1인 이웃한 장소에 사람이 있다면 0을 반환한다
    1.2. 거리가 2인 장소에 사람이 존재하고, 사이에 파티션이 없다면 0을 반환한다
2. 대각선을 확인한다
    2.1. 대각선에 사람이 존재하고, 사이에 파티션이 두 곳 다 없다면 0을 반환한다
3. 1,2번에 해당하지 않는다면 1을 반환한다

 

 

 

코드

N=5
DIR=4
dy,dx=[1,0,-1,0],[0,1,0,-1]
crs_dy,crs_dx=[1,1,-1,-1],[1,-1,-1,1]
def keep_distance(place,cy,cx):
    ## 가로,세로 확인
    for i in range(DIR):
        ny,nx=cy+dy[i],cx+dx[i]
        
        # 이웃한 위치 확인
        if 0<=ny<N and 0<=nx<N and place[ny][nx]=='P':
            return 0
        
        # 2칸 이후 위치 확인
        nny,nnx=cy+dy[i]*2,cx+dx[i]*2
        if 0<=nny<N and 0<=nnx<N and place[nny][nnx]=='P' and place[ny][nx]=="O":
            
            return 0
        
    # 사선 확인
    for i in range(DIR):
        ny,nx =cy+crs_dy[i],cx+crs_dx[i]
        if 0<=ny<N and 0<=nx<N and place[ny][nx]=='P' and (place[ny][cx]!='X' or place[cy][nx]!='X'):
            return 0
    
    return 1
    
        
def check(place):
    for i in range(N):
        for j in range(N):
            if place[i][j]=='P' and keep_distance(place,i,j)==0:
                return 0
    return 1

def solution(places):
    answer = []
    for place in places:
        answer.append(check(place))
    return answer