[프로그래머스LV2] 거리두기 확인하기

[LV2] 거리두기 확인하기 문제링크 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 www.programmers.co.kr

 

문제 해설

 

이 문제는 전형적인 탐색문제이며 bfs를 활용하면 풀 수 있는 문제이다. 다만 여기서 조건은 사람이 있는 위치에서 +2칸 이내에 사람이 있으면 안된다는 것이다 이것을 활용한 코드는 다음과 같다.

from collections import deque

dx=[-1,1,0,0]
dy=[0,0,-1,1]

def bfs(loc,place):
    que=deque([loc]) #초기값
    visited=[[False]*5 for _ in range(5)] #위치가 방문된적이 있는지 판단 리스트
    visited[loc[0]][loc[1]]=True #초기 위치 방문으로 표시
    while que:
        x,y,d=que.popleft() #x,y는 좌표 d는 현재까지의 거리
        if d>2: 만약 거리가 2가 넘어가면 중단 
            break
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<5 and 0<=ny<5 and visited[nx][ny]==False:
                if place[nx][ny]=='P' and d != 2: #사람을 만났는데 그 사람이 거리 2보다 작은 경우
                    return False #거리두기 실패 
                elif place[nx][ny]=='X': #현재 위치가 파티션인 경우 pass
                    continue
                visited[nx][ny]=True #현재위치 방문확인
                que.append((nx,ny,d+1)) #현재위치 저장
    return True
    
def solution(places):
    answer=[]
    for place in places: 
        PeopleLOC=[] #사람들의 위치를 담는 리스트 
        chk=1 #거리두기가 성공인지 판단하는 변수
        for i in range(5):#사람들의 위치 찾아서 리스트에 담기
            for j in range(5):
                if place[i][j]=='P':
                    PeopleLOC.append((i,j,0))
        for loc in PeopleLOC: # 거리두기가 잘 되고 있는지 판단하는 반복문
            if bfs(loc,place)==False:
                chk=0
                break
        answer.append(chk)
    return answer

 

FeedBack

 

• 사람들간의 거리두기 판단 조건을 애매하게 둬서 해결하는데 조금 오래 걸렸다.
• 조건이 약간은 끼워 맞춘 느낌이 있어서 다른 사람들의 코드를 보고 비교해보면서 개선 방향을 찾아봐야겠다.