거리두기 확인하기

📌 문제링크

https://programmers.co.kr/learn/courses/30/lessons/81302

 

✔️ 풀이1. BFS 알고리즘 - Queue 사용, check 함수 사용한 경우

import queue # bfs 탐색 시 사용하는 자료 구조

# 상하좌우 이동, 고정된 값이므로 tuple 사용
D = ((-1,0), (1,0), (0, -1), (0, 1)) # 위로 이동, 아래로 이동, 좌로 이동, 우로 이동

def bfs(place, row, col): # 대기실, 응시자의 위치 정보 
                        # -> 거리두기 확인 return 값 : True/False
    visited = [[False for _ in range(5)] for _ in range(5)] # 대기실 크기만큼의 방문 array
    q = queue.Queue() # queue 객체 생성
    visited[row][col] = True # 방문 표시
    q.put((row, col, 0)) # 행, 열, 거리(시작위치) tuple 형태로 입력
    
    while not q.empty():
        curr = q.get() # dequeue, 현재 좌표
        
        if curr[2] > 2 : # 거리가 2보다 클 경우 탐색 skip
            continue
        # 거리 2 이하인 경우
        if curr[2] != 0 and place[curr[0]][curr[1]] == 'P': # 다른 응시자를 만난 경우
            return False 
        # 거리 2 이하 & 다른 응시자를 만나지 않은 경우
        for i in range(4): # 상하좌우 이동
            nr = curr[0] + D[i][0]
            nc = curr[1] + D[i][1]
            if nr < 0 or nr > 4 or nc < 0 or nc > 4: # 대기실 밖일 경우
                continue
            if visited[nr][nc]: # 이미 방문한 경우
                continue
            if place[nr][nc] == 'X':
                continue
            visited[nr][nc] = True
            q.put((nr, nc, curr[2]+1))
    return True
            
            
def check(place):
    for r in range(5):
        for c in range(5):
            if place[r][c] == 'P':
                if bfs(place, r, c) == False: # bfs 호출 (거리두기 확인)
                    return False # 탐색 중단 -> answer = 0
    return True # 거리두기 모두 지키고 있는 경우 1

def solution(places):
    answer = []
    
    for place in places:
        if check(place): # 각 대기실 거리두기 확인
            answer.append(1)
        else:
            answer.append(0)
    return answer

✔️ 풀이 2. BFS 알고리즘 - Deque 사용, check 함수 대신 flag로 구분한 경우

from collections import deque

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

def bfs(candidate, place):
    queue = deque()
    visited = [[False]*5 for _ in range(5)]
    queue.append(candidate)
    cnt = 0
    
    while queue:
        x, y = queue.popleft()
        visited[x][y] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > 4 or ny <0 or ny > 4 :
                continue
            if visited[nx][ny] :
                continue
            if place[nx][ny] == 'X':
                continue
            if place[nx][ny] == 'P':
                return False
            queue.append((nx, ny))
            
        cnt += 1
        if cnt == 2:
            return True
    return True
            
def solution(places):
    answer = []
    
    for place in places:
        candidates = deque()
        flag = True
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    candidates.append((i,j))
                    
        for candidate in candidates:
            if not bfs(candidate, place):
                flag = False
                break
                
        if not flag : 
            answer.append(0)
        else : 
            answer.append(1)

    return answer

 

🔎 참고

풀이1. https://www.youtube.com/watch?v=hCVgKE6qwFs
풀이2. https://hongcoding.tistory.com/m/124