악곱 == 악성곱슬

BFS

---

해당 문제는 여러 조건이 포함된 BFS 문제이다. 기본 BFS에 몇 가지 조건을 포함해서 구현할 수 있다.

1. 판을 돌며 P를 만나면 BFS를 수행
2. BFS는 거리가 2인 노드까지만 탐색하고 조기 종료시킴
   1. 만약 수행 도중 P를 만난다면, 거리두기를 지키지 못한 것 → 종료
   2. X를 만나거나 인덱스범위 밖이라면 queue에 넣지 않고 넘어감
   3. O를 만난 일반 경우에만 queue에 넣고 계속 진행

여기서 맨해튼 거리란, 그냥 두 칸 떨어져 있다고 이해하면 된다. 참고로 유클리드 거리는 원의 반지름과 같이 직선거리이다. 자주 나오는 수학 용어이니 기억해두자.

따라서 두 칸 떨어져 있기 때문에 BFS나 DFS로 2칸의 조건을 걸고 풀면 쉽게 풀 수 있었다.

구현

---

from collections import deque

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

def bfs(place, start):
    que = deque()
    visited = [[False] * 5 for _ in range(5)]
    que.append([0, start[0], start[1]])
    visited[start[0]][start[1]] = True
    while que:
        dist, x, y = que.popleft()
        if dist == 2:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= 5 or ny >= 5:
                continue
            if visited[nx][ny]:
                continue
            if place[nx][ny] == 'X':
                continue
            # 거리 2 안에 사람 등장
            if place[nx][ny] == 'P':
                return False
            que.append([dist + 1, nx, ny])
            visited[nx][ny] = True
    return True

def solution(places):
    answer = []
    for place in places:
        starts = []
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    starts.append([i, j])
        result = 1
        for s in starts:
            if not bfs(place, s):
                result = 0
                break
        answer.append(result)
    return answer