*프로그래머스)거리두기 확인하기

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

 

쉽게 말하면, 2차원 배열 안에 P를 기준으로 거리가 2 이내에 다른 P가 있는지, 있다면 그 사이에 X가 있는지, O가 있는지 판별하는 문제이다.

from collections import deque

def bfs(x,y,arr):
    visit = [[False for _ in range(5)] for _ in range(5)]
    q = deque()
    
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    
    visit[x][y] = True
    q.append((x,y,0))
    
    while q:
        x, y, distance = q.popleft()
        if distance > 2:
            continue
        if arr[x][y] == 'P' and distance != 0:
            return False
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if (0<= nx <5 ) and (0 <= ny < 5):
                if visit[nx][ny] == False and arr[nx][ny] != 'X':
                    visit[nx][ny] = True
                    q.append((nx,ny,distance+1))
    return True                
        

def check(arr):
    for i in range(len(arr)):
        for j in range(len(arr[i])):
            if arr[i][j] == 'P':
                if bfs(i,j,arr) == False:
                    return False
    return True

def solution(places):
    answer = []
    
    arr = []
    for i in range(len(places)):
        arr2=[]
        
        for p in places[i]:
            a = list(p)
            arr2.append(a)
        arr.append(arr2)
            
            
    for place in arr:
        if check(place):
            answer.append(1)
        else:
            answer.append(0)
    
    return answer

 

2차원 배열을 보자마자, 그리고 주변의 값을 확인하는 것을 알자마자 DFS와 BFS를 떠올렸다.

여태 해왔던 BFS처럼 for문을 돌며, P가 잇는지 확인, 있다면 bfs로 넘기고 상하좌우를 확인하며 q에 append시킨다.

하지만 처음 발견한 P와 상하좌우를 돌며 위치한 거리를 어떻게 확인할 것인가에 많은 고민이 있었다.

 

x,y값을 더하고 곱하고 제곱근구하고... 등등 머리가 굳었는지 별다른 생각이 떠오르지가 않았다.

검색해본 결과 역시 큐에 넣는 값에 거리를 넣으면 되는 간단한 해결법이 있었다..ㅠ