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

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

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

내 풀이:

from collections import defaultdict
from itertools import combinations

def solution(places):
    ans = [1] * 5
    
    for idx, place in enumerate(places):
        P, OX = [], defaultdict(str)
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    P.append((i, j))
                else:
                    OX[(i, j)] = place[i][j]

        for l, r in combinations(P, 2):
            r1, c1 = l
            r2, c2 = r
            dist = abs(r1 - r2) + abs(c1 - c2)
            if dist == 1:
                ans[idx] = 0
                break
            elif dist == 2:
                if abs(r1 - r2) == 2 and OX[((r1 + r2) / 2, c1)] == 'O':
                    ans[idx] = 0
                    break
                elif abs(c1 - c2) == 2 and OX[((c1 + c2) / 2, r1)] == 'O':
                    ans[idx] = 0
                    break
                elif abs(r1 - r2) == 1 and abs(c1 - c2) == 1 and \
                    OX[(r1, c2)] == 'O' or OX[(r2, c1)] == 'O':
                    ans[idx] = 0
                    break
        
    return ans

• 아이디어: 완전탐색으로 P끼리 거리 측정하여 거리두기를 지키지 않는 경우 처리

참고 풀이:

def check(place):
    for irow, row in enumerate(place):
        for icol, cell in enumerate(row):
            if cell != 'P':
                continue
            else:
                if irow != 4 and place[irow + 1][icol] == 'P':
                    return 0
                if icol != 4 and place[irow][icol + 1] == 'P':
                    return 0
                if irow < 3 and place[irow + 2][icol] == 'P' and place[irow + 1][icol] != 'X':
                    return 0
                if icol < 3 and place[irow][icol + 2] == 'P' and place[irow][icol + 1] != 'X':
                    return 0
                if irow != 4 and icol != 4 and place[irow + 1][icol + 1] == 'P' and \
                (place[irow + 1][icol] != 'X' or place[irow][icol + 1] != 'X'):
                    return 0
                if irow != 4 and icol != 0 and place[irow + 1][icol - 1] == 'P' and \
                (place[irow + 1][icol] != 'X' or place[irow][icol - 1] != 'X'):
                    return 0
    return 1

def solution(places):
    return [check(place) for place in places]

• 다른 방식의 브루트 포스, 행렬크기가 고정인 경우 시도할 수 있는 풀이
• 순차 탐색하면서 우측 아래 방향의 거리두기 여부만 확인해도 모든 범위 커버 가능 (탐색 방향과 일치하므로)