문제 설명

전체 코드

from collections import deque

def solution(places):
    def bfs(x, y, visited):
        dx = [-1,1,0,0]
        dy = [0,0,-1,1]

        q = deque([])
        q.append([x, y])
        visited[x][y] = 1

        while q:
            x, y = q.popleft()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < len(visited) and 0 <= ny < len(visited[0]):
                    if visited[nx][ny] == 0:
                        if place[nx][ny] == 'O':
                            visited[nx][ny] = visited[x][y] + 1
                            q.append([nx, ny])
                        elif place[nx][ny] == 'P':
                            if visited[x][y] <= 2:
                                return 0
                            else:
                                visited[nx][ny] = 1
                                q.append([nx, ny])
        return 1       

    answer = []
    for place in places:
        visited = [[0]*len(place[i]) for i in range(len(place))]
        ret = []
        for i in range(len(place)):
            for j in range(len(place[i])):
                if place[i][j] == 'P' and visited[i][j] == 0:
                    ret.append(bfs(i, j, visited))

        if 0 in ret:
            answer.append(0)
        else:
            answer.append(1)
    
    return answer

해결 방법

내 기억상 코딩테스트 때는 잘 못풀었던 문제로 기억하는데 지금 풀어보니 쉽게 풀린 문제다. 가장 기초적인 bfs 문제로 P사이의 거리를 계산하고 2이하이면 거리두기를 하지 않은 것이므로 0을 return 하고 그게 아니라면 1을 return 하면 되는 문제이다.