[프로그래머스]#거리두기확인하기: 백트레킹/ lv2

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

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

🚩제출한 코드

"""
- 5x5/응시자간의 거리 >2 유지
    (1) 파티션 중간 배치할 경우 -> 가능 
    (2) 대각선 배치 
        2-1. 반대 대각선에 모두 "파티션 존재함" -> 가능
        2-1. 1개라도 빈 테이블 존재함 -> 불가능 
    (3) 그외 거리 >2 인 경우 -> 가능
- 응시자 위치 P , 빈테이블 O , 파티션 X 
- output : 5개의 대기실에서 각각 거리두기 충족 여부 (1 , 0 )
# flow(BFS?)
1. 입력 변수 정의
    - 응시자 P의 위치 정보 저장
2. 주변 응시자 P의 위치 탐색 
    => 맨허튼 거리 2 까지(lv=2) 탐색
    P -> No
    x -> YES
    O -> 다음 level로 이동하기
"""
from collections import deque

dy =[1,-1,0,0] ; dx=[0,0,-1,1]         
def solution(places):
    answer = []
    for place in places : 
        # 1. 응시자 위치 확인 
        people = []
        for i in range(5) :
            for j in range(5) :
                if place[i][j] == "P":
                    people.append([i,j])
        #2. 응시자 별로 거리 확인하기
        def bfs(start):
            clv = 0 
            visited = [[-1]*5 for _ in range(5)] # 거리 저장하기(lv)
            q = deque([start]) 
            visited[start[0]][start[1]] = 0 
            while q  :
                cy,cx = q.popleft()
                clv = visited[cy][cx]
                if clv >= 2 : 
                    break
                for d in range(4):
                    ny,nx = cy + dy[d] , cx +dx[d]
                    if 0<= ny < 5 and 0 <= nx < 5 and visited[ny][nx] <= -1  : 
                        if place[ny][nx] == "X": 
                            visited[ny][nx] = clv +1 
                            continue
                        elif place[ny][nx] == "O":
                            q.append([ny,nx])
                            visited[ny][nx] = clv +1 
                        elif place[ny][nx] == "P" :
                            return False 
            return True 
        flag = True
        for p in range(len(people)):
            start = people[p]
            flag = bfs(start) 
            if not flag : 
                break
        if flag: 
            answer.append(1)
        else :
            answer.append(0)
        
            
    # print(people)
    # print(f"answer{answer}")
    return answer

• 💥 1차 제출

🚩결과

💡TIL