[프로그래머스, 2021 카카오 인턴쉽] 거리두기 확인하기 python

https://programmers.co.kr/learn/courses/30/lessons/81302?language=python3 

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

 

1. 해설

아래와 같은 로직을 구현하면 된다.

 

1. 지원자들의 위치를 담고 있는 리스트를 만든다.(loc_p)

2. 그 리스트로부터 중복없이 2명을 뽑아 이 두명이 적절한 거리두기를 하고 있는지 확인한다.

3. 거리두기 로직은 다음과 같다.

    1. BFS로 탐색하지 못하면 => 거리두기 만족(True)

    2. BFS로 탐색 가능하지만 두 사람의 맨해튼 거리가 2 이상이면 거리두기 만족(True)

    3. 위 두조건이 아니면 False

4. 모든 쌍에 대해서 True라면 해당 대기장소는 True 아니면 False

 

약간 까다로운 점은 맨해튼 거리를 매번 구해주는게 아니라 visited 리스트에 저장해서 사용하는 점과 BFS 탐색시 다른 지원자를 만났을 때 어떻게 해야하는지였다.

 

def bfs(start, target, place):
	
    """ 
    start로 부터 target가 서로 거리두기를 하는지 확인하는 함수
    BFS로 탐색하면서 start가 target에 도착 불가능하면 => True 
    도착해도 맨해튼 거리가 2 이상이라면 => True
    둘다 아니면 => False
    
    맨해튼 거리는 따로 계산하지 않고 visited에 저장해서 사용했다.
    """
    
    # 초기화 부분
    N=5
    q = [start]
    visited = [[-1 for i in range(N)] for i in range(N)]
    visited[start[0]][start[1]] = 0 
    moves =[[1,0],[0,1],[0,-1],[-1,0]]
    
    #q가 빌 때까지
    while q:
        r, c = q.pop(0)
        
        #만약 현재 위치가 찾던 위치라면
        if (r,c) == target:
            if visited[r][c] > 2: #시작지점에서 맨해튼 거리를 visited에서 확인 후 2 초과라면
                return True
            return False
            
        #상하 좌우로 움직임
        for dr, dc in moves:
            nr, nc = r+dr, c+dc
            
            #place를 벗어나면 다시 계산
            if nr <0 or nr >= N or nc < 0 or nc >= N or place[nr][nc] == "X":
                continue
               
            #방문하지 않았다면
            if visited[nr][nc] == -1:
            	#시작점으로부터 거리를 업데이트하고
                visited[nr][nc] = visited[r][c] + 1
                #큐에 넣어준다.
                q.append((nr, nc,))
    #target에 도착하지 못했다면 거리두기를 잘하고 있음으로 True 반환    
    return True
    
def is_proper_distance(place):
	""" 적절한 거리두기를 하고 있는지 확인하는 함수"""
    
    N = len(place)
    loc_p = []
    
    #대기 장소를 돌면서 지원자들의 위치를 확인한다.
    for i in range(N):
        for j in range(N):
            if place[i][j] == "P":
                loc_p.append((i,j,))
                
    #지원자들 리스트에서 중복없이 2개를 뽑는다.
    for i in range(len(loc_p)):
        for j in range(i+1, len(loc_p)):
            start, target = loc_p[i], loc_p[j]
            #거리 두기 조건을 확인한다.
            isContent = bfs(start, target, place) 
            #만족하지 못했다면 False 반환
            if not isContent:
                return False
    # 모든 쌍에 대해 만족했다면 True 반환
    return True
            
                
def solution(places):
    answer = []
    
    for place in places:
    	#해당 장소가 적절한 거리두기를 확인해서
        result=is_proper_distance(place) 
        if result:         # 결과가 참이면 1을 넣고
            answer.append(1)
        else: #아니면 0을 넣는다
            answer.append(0)
      
    return answer