[파이썬] 프로그래머스 : 거리두기 확인하기 (Lv.2)

[파이썬] 프로그래머스 : 거리두기 확인하기 (Lv.2)

 

프로그래머스

 

---

풀이

0. 방향성 생각

전체 입력이 5x5이고 테케 5번처럼 사람이 최대한 많아봐야 13명이라 13C2 = 78로 이런 케이스 5개 들어와도 충분히 적은 케이스라서 완전탐색으로 구현했다.

BFS로 인접거리 2인 부분까지 탐색하는 거로도 풀 수 있어보였는데 그냥 구현하는게 더 빠를거같아서 완탐 풀이.

 

1. 입력 받기

from itertools import combinations as C
def solution(places): # 완탐
    
    answer = []
    for case in places:
        temp = []
        for i in case:
            temp.append(list(i))

        location = []
        for y in range(5):
            for x in range(5):
                if temp[y][x] == 'P':
                    location.append((x,y))

location 리스트에 사람이 존재하는 모든 좌표를 넣는다

 

1. 거리가 1인 사람쌍 거르기

        pair = list(C(location,2)) 
        dist_2 = []
        warn = False
        
        for p1,p2 in pair:
            d = sum(list(map(lambda x,y:abs(x-y), p1,p2))) # 모든 순서쌍 거리 조사
            if d == 1:
                warn = True
                answer.append(0)
                break
            if d == 2:
                a = [p1,p2]
                a.sort()
                dist_2.append(a)
                
        if warn :
            continue

조합을 활용해서 pair에 순서쌍을 다 넣는다.

warn을 사용해서 True가 되면 거리두기 실패를 알린다.

d=1인 경우 이미 실패한 케이스이므로 break를 해주고 if문으로 다음 테스트 케이스로 넘어간다.

d=2인 경우 좌표쌍을 dist_2에 넣는다.

 

2. 거리가 2인 사람쌍 거르기

        dist_2.sort(key=lambda x:(x[0],x[1]))        
        for p1,p2 in dist_2:
            x1,y1 = p1
            x2,y2 = p2
            if y1==y2 :
                if temp[y1][x1+1] == 'O':
                    warn = True
                    break
            elif x1==x2 :
                if temp[y1+1][x1] == 'O':
                    warn = True
                    break
            elif x1+1==x2 and y1+1==y2 :
                if temp[y1+1][x1] == 'O' or temp[y1][x1+1] == 'O':
                    warn = True
                    break
            elif x1+1==x2 and y1-1==y2 :
                if temp[y1-1][x1] == 'O' or temp[y1][x1+1] == 'O':
                    warn = True
                    break
                    
        if warn : answer.append(0)
        else : answer.append(1)
        
    return answer

 

P?
?P

?P
P?

P?P

P
?
P

 

이러한 4가지 경우에 ?에 있는 부분을 조사해주면 된다.

dist_2에 추가할 정렬해서 넣어서 가장 왼쪽에 있는 사람 P1의 좌표를 기준으로 인덱스를 쓴다.

---

전체코드

from itertools import combinations as C
def solution(places): # 완탐
    
    answer = []
    for case in places:
        temp = []
        for i in case:
            temp.append(list(i))

        location = []
        for y in range(5):
            for x in range(5):
                if temp[y][x] == 'P':
                    location.append((x,y)) 
                    
        pair = list(C(location,2)) 
        dist_2 = []
        warn = False
        
        for p1,p2 in pair:
            d = sum(list(map(lambda x,y:abs(x-y), p1,p2))) # 모든 순서쌍 거리 조사
            if d == 1:
                warn = True
                answer.append(0)
                break
            if d == 2:
                a = [p1,p2]
                a.sort()
                dist_2.append(a)
                
        if warn :
            continue
            
        dist_2.sort(key=lambda x:(x[0],x[1]))        
        for p1,p2 in dist_2:
            x1,y1 = p1
            x2,y2 = p2
            if y1==y2 :
                if temp[y1][x1+1] == 'O':
                    warn = True
                    break
            elif x1==x2 :
                if temp[y1+1][x1] == 'O':
                    warn = True
                    break
            elif x1+1==x2 and y1+1==y2 :
                if temp[y1+1][x1] == 'O' or temp[y1][x1+1] == 'O':
                    warn = True
                    break
            elif x1+1==x2 and y1-1==y2 :
                if temp[y1-1][x1] == 'O' or temp[y1][x1+1] == 'O':
                    warn = True
                    break
                    
        if warn : answer.append(0)
        else : answer.append(1)
        
    return answer

 

코멘트

코드가 좀 못생기긴 했다.

제어문만 좀 잘 써주면 쉽게 풀이 가능