[2021 카카오 채용연계형 인턴십][lv.2] 거리두기 확인하기 (파이썬Python, BFS)

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

프로그래머스

 
프로그래머스 > 코딩테스트 연습 > 2021 카카오 채용연계형 인턴십 > 거리두기 확인하기
 
 

---

 

문제

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.대기
 

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
 
 
제한사항

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로 길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

 
 

places	result
[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]	[1, 0, 1, 1, 1]

 
 

✅ 풀이 과정

0.  자료구조 / 알고리즘 선택

P가 존재하는 곳에서부터 거리가 2까지 BFS를 돌린다. 
만약 BFS가 동작하는동안 사람이 존재하면, False를 리턴, 
존재하지 않으면 True를 리턴하면 된다.
 
 

1. 복잡도 고려

테스트케이스의 개수가 5개 * (5*5행열)이므로 복잡도를 고려하지 않아도 된다.
만약 조금 더 효율적으로 작성 가능한부분이 보일때마다 개선할 수 있을것 같다.
 

2. 수도코드/ 알고리즘 생각

 

✏️ Solution

1) 일단 사람의 위치를 찾는다. 
persons는 2차원으로 persons[room][r, c]를 의미한다.
 
2) room마다 거리두기 여부를 확인해야하므로 반복문으로 room number를 만든다.
3) 해당 room에 존재하는 사람의 위치를 기반으로 BFS를 돌린다.
4) 사람이 안전한위치에 존재하면 safe변수에 True값이 들어올텐데 count_safe를 증가시켜서 해당 room에 있는 모든 사람이 안전한지 체크한다.
5) 모든 사람이 안전하다면 answer 리스트에 1을 , 아니라면 0을 추가한다.
 

✏️  bfs

1) 큐와 방문처리 배열을 만든다.
큐에는 시작한 사람의 위치(r,c)를 추가해준다. 
방문처리 배열은 2차원으로 0으로 초기화하고, 시작한 사람의 위치에 1을 할당한다. (0이면 아직 방문하지 않은것)
(방문처리 배열 : 시작한 사람의 위치에서 맨해튼 거리를 계산해 저장함과 같다.)
 
2) 큐가 빌때까지 반복한다.
r, c로 현재 위치를 뺀다.
 
3)  4가지 방향에 대해서 dr, dc 이동 좌표를 만든다.
해당 좌표가 내부공간이면서 + X가 아니고 + 아직 방문을 안했는지 체크한다.
 
-- 만약 현재까지 방문한 곳 + 1의 값이 3보다 크다면 거기는 더이상 보지 않아도 된다 (시작한 사람을 1로 시작해서 맨해튼 2까지 봐야하므로 3까지만 체크하면 된다)
 
--  여기까지 왔다면 P이거나 O인경우이다
  P인경우 이 사람이 맨해튼 거리가 3과 같거나 작은지 체크한다.  ->> 3보다 작거나 같으면 거리두기가 제대로 지켜지지 않은것이므로 바로 False를 반환한다.
 
 
P와 O,  두 경우 모두 해당 좌표까지 몇의 맨해튼 거리로 도달할수있는지 봐야하므로 마지막에 visited를 계산해준다.
  Visited[dr][dc] = visited[r][c]+1 
  해당 좌표를 큐에 넣으며 BFS를 계속한다.
 
4)  마지막에 While문이 종료된 경우까지 왔다면 해당 사람에 대해 거리두기가 잘 지켜진 것이므로 True를 반환한다.
 
 
 

✅ 내가 쓴 정답코드

from collections import deque

SIZE = 5
d = [[-1,0],[0,1],[1,0],[0,-1]]


def findPerson(places):
    persons = [[] for _ in range(SIZE)]

    for room in range(SIZE):
        for r in range(SIZE):
            for c in range(SIZE):
                if places[room][r][c] == 'P':
                    persons[room].append([r,c])
    return persons

def solution(places):
    answer = []
    #Person의 위치 찾기 
    persons = findPerson(places) #persons[room][r][c]
        
    #모든 Person에 대해 BFS를 돌린다 (맨해튼거리가 2이하인데 P가 있으면 탈출)
    for room in range(SIZE):
        room_persons = persons[room]
        
        count_safe, room_safe = 0, 0 #플래그를 위한 초기화
        
        for r, c in room_persons:
            safe = bfs(r,c, places[room])
            if safe :
                count_safe +=1
        
        if count_safe == len(room_persons):        
            room_safe = 1
            
        answer.append(room_safe)
            
    return answer

def printRoom(room):
    for i in range(SIZE):
        for j in range(SIZE):
            print(room[i][j] ,end="")
        print()
        
    print()

def bfs(r, c, room):
    
    queue = deque()
    queue.append([r,c])
    
    visited = [[0] * SIZE for _ in range(SIZE)]
    visited[r][c] = 1 #1로 초기화했으므로 3까지가 불가능한거임 ...
    
    while queue:
        r,c = queue.popleft()
    
        for i in range(4):
            dr = r + d[i][0]
            dc = c + d[i][1]

            if (0<=dr<SIZE) and (0<=dc<SIZE) and room[dr][dc] != 'X' and not visited[dr][dc]: #내부공간확인

                if visited[r][c] + 1 > 3:
                    continue
                
                if room[dr][dc] == 'P': #사람이다
                    #이 사람의 맨해튼 거리가 2이상인지 체크한다.
                    if (visited[r][c] + 1 <= 3) : # 초기화를 1로 했기 떄문에 3으로 체크함.
                        return False
                        
                visited[dr][dc] = visited[r][c] +1
                queue.append([dr,dc])
    
    return True

 
 
 

---

references

프로그래머스