[알고리즘] 거리두기 확인하기

sith-call.dev·2023년 4월 18일

알고리즘

목록 보기

4/47

from collections import deque

class Node():
    def __init__(self, y, x, level=0):
        self.x = x
        self.y = y
        self.level = level
        

def bfs(start: Node, matrix: list)->int:
    visited = [[0 for _ in range(5)] for _ in range(5)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    q = deque()
    q.append(start)
    visited[start.y][start.x] = 1
    
    while len(q) != 0:
        now = q.popleft()
        # print(f"{now.x} {now.y} {now.level}")
        
        if now != start and matrix[now.y][now.x] == "P":
            # print(f"cath! {now.x} {now.y} {now.level}")
            return now
        
        for i in range(4):
            nx = now.x + dx[i]
            ny = now.y + dy[i]
            if nx < 0 or ny < 0 or nx >= 5 or ny >= 5:
                continue
            if matrix[ny][nx] == "X":
                continue
            if visited[ny][nx] == 1:
                continue
            # print(f"next! {nx} {ny} {now.level+1}")
            q.append(Node(ny, nx, now.level+1))
            visited[ny][nx] = 1
    
    # 찾지 못한 경우 -1 반환
    return Node(0,0,-1)
    

def solution(places):
    answer = []
    # 모든 place에서 검사를 한다.
    for place in places:
        is_next_place = False
        # 한 place 내부의 모든 좌표에서 거리를 계산해본다.
        for y in range(len(place)):
            is_escape_from_this_spot = False
            for x in range(len(place[0])):
                if place[y][x] == "P":
                    node = bfs(Node(y, x), place)
                    # 한 좌표에서 어느 곳에서도 P를 못 찾은 경우 다음 좌표를 검사한다.
                    if node.level == -1:
                        continue
                    # 한 좌표에서 거리가 2 이하인 P를 찾은 경우 0을 표기하고 다음 place로 넘어간다.
                    if node.level <= 2:
                        is_escape_from_this_spot = True
                        break
            if is_escape_from_this_spot:
                is_next_place = True
                break
        if is_next_place:
            answer.append(0)
            continue
        # 모든 좌표를 검사했음에도 거리가 2 이하인 점을 찾지 못했다면 1을 표기하고 다음 place로 넘어간다.
        answer.append(1)
    return answer

놓친 점

한 좌표에서 어느 곳에서도 다른 P를 못 찾은 경우에느 다음 좌표로 넘어가야 했는데, 이 부분에서 break를 해버렸다. 이를 continue로 바꿔주고 테스트 케이스를 모두 해결할 수 있었다.

문제가 풀리지 않는다면?

큰 흐름에서 알고리즘의 과정을 다시 생각해본다.
큰 흐름을 미시적인 관점에서 다시 생각해본다.
a. 특히 큰 흐름 간의 전환이 일어나는 부분에서 발생할 수 있는 엣지 케이스를 생각해본다.
흐름을 모두 검토해봤다면 흐름과 코드 사이에 맵핑이 잘 되어 있는 지 확인한다.

흐름

모든 대기실을 확인한다.
한 대기실의 모든 좌표에서 거리를 계산한다.
a. bfs를 통해 맨해튼 거리를 계산한다.
b. 2 이하의 거리에선 맨해튼 거리와 bfs를 통한 최소 거리가 동일하다.
c. 이러한 사실을 증명한 뒤에 bfs를 도입한다.
좌표에서 계산된 거리가 2 이하인 경우에 0을 답지에 표기하고 다음 대기실을 검토한다.
좌표에서 계산된 거리가 2 초과인 경우에는 다음 좌표를 계산한다.
한 좌표에서 거리를 구할 수 없는 경우에도 다음 좌표를 계산한다.

bfs를 사용한 이유

벽이 존재하는 상황에서 맨해튼 거리를 구하기 위해선 중간에 벽이 있는지 확인해야 했다. 이런 경우에는 모든 경우를 예측해서 대비해야만 문제를 풀 수 있었기에 휴먼 에러에 취약한 코드가 만들어질 것이라 생각했다. 따라서 보다 더 보편적으로 많은 경우를 처리할 수 있는 bfs를 사용했다.