[알고리즘/파이썬] 프로그래머스 - 거리두기 확인하기

문제

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

프로그래머스

 

풀이

맨해튼 거리가 2인 경우를 크게 3가지로 나눠서 확인했다.

1. 맨해튼거리가 1인 경우 중 동서남북 1칸 차이인 경우

-> 이 때는 칸막이고 뭐고 체크할 필요 없이 P가 나오면 무조건 거리두기 F

2. 맨해튼거리가 1인 경우 중 대각선 1칸 차이인 경우

-> 이 때는 사이에 칸막이가 있는지 체크해야한다. 만약 (1,-1) 만큼 차이 나는 경우 (0,-1) , (1,0) 이 칸막이(X)인지 확인하면 된다.

3. 맨해튼거리가 2인 경우 ( 동서남북 2칸 차이인 경우 )

-> 이 때는 그 사이 값(동서남북 1칸 차이)이 칸막이(X)인지 체크하면 된다.

 

모든 경우를 체크해주면 끝

 

코드

def solution(places):
    answer = []
    
    # 체크할 필요가 없이 이 범위에서 p가 나오면 무조건 거리두기 안 지킴
    one_dx = [1,-1,0,0]
    one_dy = [0,0,-1,1]
    
    # 사이가 모두 파티션(X)인지 체크 / 사이 값 -> [0][dx] , [dy][0]
    cross_dx = [1,1,-1,-1]
    cross_dy = [-1,1,-1,1]

    # 사이가 파티션(X)인지 체크
    line_dx = [2,-2,0,0]
    line_dy = [0,0,-2,2]
    
    line_check_dx = [1,-1,0,0]
    line_check_dy = [0,0,-1,1]
    
    def check(place,x,y):
        for i in range(4):
            nx = x+one_dx[i]
            ny = y+one_dy[i]
            
            if nx<0 or ny<0 or nx>=5 or ny>=5:
                continue
            if place[nx][ny] == 'P':
                return False
        
        for i in range(4):
            nx = x+cross_dx[i]
            ny = y+cross_dy[i]
            
            if nx<0 or ny<0 or nx>=5 or ny>=5:
                continue
            if place[nx][ny] == 'P':
                if place[x][ny] !='X' or place[nx][y] != 'X':
                    return False
        
        for i in range(4):
            nx = x+line_dx[i]
            ny = y+line_dy[i]
            
            if nx<0 or ny<0 or nx>=5 or ny>=5:
                continue
            check_x = x+line_check_dx[i]
            check_y = y+line_check_dy[i]
            
            if check_x<0 or check_y<0 or check_x>=5 or check_y>=5:
                continue
            
            if place[nx][ny] =='P' and place[check_x][check_y] != 'X':
                return False
            
        return True
            
    
    for place in places:
        flag = 1
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    result = check(place,i,j)
                    if not result:
                        flag = 0
                        break
            if flag == 0:
                break
        
        if flag == 0:
            answer.append(0)
        else:
            answer.append(1)
                    
                    
    
    return answer