거리두기 확인

코딩테스트 연습 - 거리두기 확인하기 | 프로그래머스 (programmers.co.kr)

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

 

풀이)

접근방식)

응시자들 간의 거리를 확인하기 위해서는 응시자들의 좌표를 알아야 한다고 생각하여 응시자들의 (x,y)좌표를 리스트에 저장했고 응시자들끼리의 거리두기 여부를 확인했다.

맨해튼 거리 == 2

맨해튼 거리가 2인 위 그림과 같은 모든 경우에 거리두기 수칙이 지켜지는지를 체크했다.

맨해튼 거리가 1인 경우에는 0을 리턴했고 3 이상인 경우에는 1을 리턴했다.

 

알고리즘)

• places를 이용해 대기실을 표현하는 리스트 생성
• 리스트를 확인하면서 응시자가 있는 위치 좌표를 저장
• 각 응시자들의 거리두기를 체크
• 각 대기실별로 거리두기 예방 수칙 준수 여부를 확인 

코드)

import copy
array = [[0 for col in range(5)] for row in range(5)]

def check(x1,y1,x2,y2):
        #print("x1 = {} y1 = {},  x2 = {} y2 = {} ".format(x1,y1,x2,y2),end = ":  ")
        if (abs(x1 - x2) + abs(y1 - y2)) > 2: # 맨해튼 거리 3이상
            return 1
        elif (abs(x1 - x2) + abs(y1 - y2)) ==1: #맨해튼 거리 1
            return 0
        else: # 맨해튼 거리 2
            if(x1 - x2 == -2 and y1 - y2 == 0): #완쪽으로 한칸 건너뛰고 사람
                if(array[y1][x1+1] == "O"):
                    return 0
            elif( x1 - x2 == 2 and y1 - y2 == 0): #오른쪽으로 한칸 건너뛰고 사람
                if(array[y1][x1-1] == "O"):
                    return 0
            elif( x1 - x2 == 0 and y1 - y2 == -2): #=아래 한칸 건너뛰고 사람
                if(array[y1+1][x1] == "O"):
                    return 0
            elif( x1 - x2 == 0 and y1 - y2 == 2): #위 한칸 건너뛰고 사람
                if(array[y1-1][x1] == "O"):
                    return 0    
            elif( x1 -x2 == 1 and y1 -y2 == 1): # 왼쪽 위
                if(array[y1 - 1][x1] == "O" or array[y1][x1 - 1] == "O"):
                    return 0
            elif( x1 - x2 == 1 and y1 - y2 == -1): #왼쪽 아래
                 if(array[y1 + 1][x1] == "O" or array[y1][x1 - 1] == "O"):
                    return 0
            elif( x1 - x2 == -1 and y1 - y2 == 1): #오른쪽 위
                 if(array[y1 - 1][x1] == "O" or array[y1][x1 + 1] == "O"):
                    return 0
            elif( x1 - x2 == -1 and y1 - y2 == -1): # 오른쪽 아래
                   if(array[y1 + 1][x1] == "O" or array[y1][x1 + 1] == "O"):
                    return 0
        return 1

def solution(places): 
    answer = []
    n = 0
    for matrix in places:  #
        i = 0
        answer.append(1) # 기본값은 성공
        for c in matrix: # 행렬값 -> array 복사
            array[i] = c[:]
            i += 1
    
        person = []
        for i in range(5):
            for j in range(5):
                line = []
                if array[i][j] =="P":  # 사람이 있는 좌석 좌표 저장
                    line.append(i)
                    line.append(j)
                    person.append(line)     
                
        c = 1 # check 성공/실패 여부
        for i in range(len(person)-1):
            for j in range(i+1,len(person)):
                c = check(person[i][1],person[i][0],person[j][1],person[j][0]) #응시자별 거리두기 체크
                if c == 0:
                    answer[n] = 0
      
        n += 1 # 대기실 번호

    return answer