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

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/81302

검사했던 부분을 다시 검사해야 하기 때문에 비효율 적이지만,
데이터가 5X5 행렬 5개뿐이라
BFS를 쓰지 않고 풀 수 있을 것 같았다.

전체 코드

---

def solution(places):
    answer=[]
    for room in places:
        illigal=False

        for x in range(4):
            for y in range(4):
                squere=room[x][y:y+2]+room[x+1][y:y+2] #2X2 사각형 만들기
                if (squere.count("P")>=2) and ("O" in squere): #대각선 체크
                    illigal=True

        for x in range(5):
            if ("PP" in room[x]) or ("POP" in room[x]): #행 체크
                illigal=True
            column=''.join([room[i][x] for i in range(5)]) #열 체크
            if ("PP" in column) or ("POP" in column):
                illigal=True

        answer.append(+(not illigal))
    return answer

요약

---

1. 대각선으로 앉은 경우 2X2 사각형 안에 P가 2개이상, O가 1개이상 존재하면 거리두기 어긴것.
2. 가로나 세로의 경우 한 줄 안에 "POP"나 "PP"가 존재하면 거리두기를 어긴 것.

---

해설

---

1. 대각선인 경우

대각선의 경우 거리두기를 어긴 경우, 거리두기를 지킨 경우는 다음과 같다.

거리두기를 어긴 경우의 공통점은
2X2 사각형 안에 "P"가 2개 그리고 O가 1개이상 존재한다는 것이다.
사각형 안에 "P"가 3개나 4개여도 거리두기를 어긴 경우이다.
("PP"가 필연적으로 존재하기 때문에)

if (squere.count("P")>=2) and ("O" in squere): #대각선 체크
#if (사각형 안에 "P"가 2개 이상 and "O"이 사각형 안에 존재):
    illigal=True

따라서 다음과 같이 2X2사각형의 좌측 상단 기준으로 (0,0) 부터 (3,3)까지 반복문을 돌면서 P가 2개 이상이고 O가 존재하는지 체크해준다.
(인덱스를 넘어가지 않게 (4,4)가 아니라 (3,3)까지만)

2. 가로나 세로인 경우

if ("PP" in room[x]) or ("POP" in room[x]):
    illigal=True

"PP"나 "POP"가 X번째 행 안에 들어있는지 체크해준다.

열도 같은 방식으로 검사해준다.

column=''.join([room[i][x] for i in range(5)]) #열 체크
if ("PP" in column) or ("POP" in column):
    illigal=True

---

실행 결과

---

데이터가 적어서 이렇게 풀어도 0.12ms가 최대였다.
심지어 for문에서 break도 쓰지 않았었다.

 

원본 작성일 : 2022년 5월 7일