[2021 카카오 채용연계형 인턴십] 거리두기 확인하기

https://programmers.co.kr/learn/courses/30/lessons/81302?language=python3#fn1

코딩테스트 연습 - 거리두기 확인하기

 

 

- 풀이

 

탐색을 활용해 풀어볼까도 했는데, 대기실 5개에 한 대기실이 5x5로 반복횟수가 그리 많지 않아서

아래와 같이 경우를 고려해 풀이했다.

 

P가 다음과 같을 때, P에 대해 맨허튼 거리가 2이하인 경우는 다음의 숫자로 표시된 구역과 같다.

따라서, 아래 3가지 경우를 고려하면된다.

1. 같은 행에 위치해있을때 → 사이에 칸막이가 존재하면 방역수칙 준수

2. 같은 열에 위치해있을때 → 사이에 칸막이가 존재하면 방역수칙 준수

3. 대각선에 위치해있을때 → 양 옆에 칸막이가 존재하면 방역수칙 준수, (두 사람이 2와 P라면, 3과6에는 칸막이가 존재해야한다.) 

 

맨허튼 거리가 2인 두점 2와 P

#대기실 5개, 각 대기실은 5x5
#맨허튼 거리는 최소 3, 단 파티션으로 막혀있음 허용
def solution(places):
    answer = []
    for p in places:
        answer.append(check(p)) #한개 대기실 씩 체크 후, 결과값인 0또는 1을 추가
    return answer

def manhattan(x1,y1,x2,y2): #맨허튼 거리 반환
    return abs(x1-x2) + abs(y1-y2)

def check(place):    #방역o 1, 방역x 0
    plist = []
    for i in range(5):
        place[i] = list(place[i])
    for i in range(5):         
        for j in range(5):
            if place[i][j]=='P':    #P를 만나면 루프문 시작
                for k in plist:
                    r = manhattan(k[0], k[1], i, j) #x1, y1, x2, y2
                    if r==1:    return 0
                    elif r==2:
                        if k[0]==i and place[i][int((k[1]+j)/2)]=='X':  continue    #같은 행에 있는 경우
                        elif k[1]==j and place[int((k[0]+i)/2)][j]=='X':    continue    #같은 열에 있는 경우
                        elif place[k[0]][j]=='X' and place[i][k[1]]=='X':   continue#대각선 위치에 있는 경우
                        else:   return 0          #거리가 2인경우는 위의 3가지 밖에 없으므로, 나머지는 다 0을 반환
                plist.append([i, j])
    return 1