프로그래머스 Level 2 거리두기 확인하기

그냥 조건문(노가다), DFS, BFS 등의 방식으로 풀 수 있는 문제이다.

나는 BFS 알고리즘을 사용해서 풀었다.

place에 map함수를 쓴 이유는 place가 문자열로 이루어진 리스트이기 때문이다.

예를 들어 place[0]이 문자열이라 place[0][0] = 'X'이 안된다. 그래서 쓰기 쉽게 map함수를 써서 리스트로 바꿔줬다.

 

풀이

1. place 탐색 -> place의 현재 위치가 'P'라면 'X'로 바꾸고 BFS 탐색 시작

2. BFS 탐색)

   상하좌우로 탐색하는데 맨 처음 탐색 시작 위치(i, j)와 다음 위치(Y, X)의 맨헤튼 거리가 2 이하일 경우에만 진행한다.

   다음 위치가 'O' 라면 현재 위치를 'X'로 바꾸고 계속 탐색 진행

   다음 위치가 'P'라면 거리 두기 위반이므로 바로 0 리턴

3. 한 명이라도 위반하면 0을 리턴해야 되므로 BFS 탐색이 끝날 때마다 check &= bfs(i, j) 같은 방식으로 check를 업데이트

4. 작은 반복문 끝날 때마다 ans에 check를 추가  

 

import sys
sys.setrecursionlimit(10000)

def solution(places):    
    def bfs(i, j):
        q = [(i, j)]
        while q:
            y, x = q.pop(0)
            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                Y, X = y+dy, x+dx
                if 0 <= Y < 5 and 0 <= X < 5 and abs(Y-i) + abs(X-j) <= 2:
                    if place[Y][X] == 'O':
                        place[Y][X] = 'X'
                        q.append((Y, X))
                    elif place[Y][X] == 'P':
                        return 0
        return 1
    
    ans = []
    for place in places:
        place = list(map(list, place))
        check = 1
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    place[i][j] = 'X'
                    check &= bfs(i, j)
        ans.append(check)                       
                    
    return ans