프로그래머스 lv2 - 거리두기 확인하기

문제

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

프로그래머스

 

 

접근방법

• input에 들어오는 2차원 배열의 각 행이 하나의 test case로 생각될 수 있고, 각 행들은 적절한 문자열 처리를 하면 2차원 배열로 다시 만들 수 있다.
• 이 2차원 배열이 문제의 조건인 맨해튼 거리 2 이하로 모든 사람이 배치되어 있는지 확인하는 문제이다.
• 처음 문제를 해결할 때 DFS로 해결했었다. 각 방을 탐색하며 원래 위치와 현재 위치의 좌표를 이용해 맨해튼 거리를 구하고, 거리가 2를 초과하게 되면 더 탐색하지 않고 종료하는 방식을 썼다.
• 문제를 해결하고 조금 뒤에 생각해보니 DFS로 풀 이유가 없었다. 맨해튼 거리의 정의를 잘 살펴보면 우리가 BFS에서 상하좌우를 탐색할 때 원래 위치와 현재 탐색하는 위치의 거리와 동일하기 때문에 BFS로 푸는게 성능 면에서 더 좋을 것이라는 생각이 들었다.
• 탐색 거리의 제한은 이후 이동할 거리가 적힌 visited[y][x]를 이용하여 queue에 좌표를 넣을지 말지를 조건문으로 구현하여 만들 수 있다.

 

 

정답 코드

from collections import deque

def solution(places):
    answer = []
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    
    for i in range(5):
        tmp = places[i]
        flag = True
        visited = [[0 for _ in range(5)] for _ in range(5)]
        
        board = []
        for element in tmp:
            board.append(list(element))
        
        for j in range(5):
            for k in range(5):
                queue = deque()
                if board[j][k] == 'P':
                    queue.append([j, k])
                    visited[j][k] = 1
                
                while queue:
                    y, x = queue.popleft()
                    
                    for d in directions:
                        ny = y + d[0]
                        nx = x + d[1]
                        
                        if ny < 0 or ny >= 5 or nx < 0 or nx >= 5:
                            continue
                        if board[ny][nx] != 'X' and not visited[ny][nx]:
                            visited[ny][nx] = visited[y][x] + 1
                            
                            if board[ny][nx] == 'P':
                                flag = False
                                break
                            
                            if visited[ny][nx] <= 2:
                                queue.append([ny, nx])
                    
                    if not flag:
                        break
                if not flag:
                    break
            if not flag:
                break
        if not flag:
            answer.append(0)
        else:
            answer.append(1)
            
    return answer

• visited[ny][nx] <= 2 에 대해 의문점이 생길 수 있다. 이는 다음과 같은 이유로 성립할 수 있다.
  • queue에는 거리가 2(실제 거리는 1이다 초기에 queue에 넣을 때 visited가 1임에 유의하라)인 좌표들이 들어가지만 queue가 빌 때 까지 BFS를 수행하므로 거리가 3(실제 거리는 2)인 좌표들도 자동으로 확인하게 된다.
• 혹시나 DFS로 해결할 때 도움을 줄 수 있게 하기 위해 아래는 DFS로 해결하였던 코드이다.

directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
well_ruled = True

def dfs(y, x, pivot_y, pivot_x, visited, board):
    global well_ruled
    visited[y][x] = True
    
    for d in directions:
        ny = y + d[0]
        nx = x + d[1]
        
        if ny < 0 or ny >= 5 or nx < 0 or nx >= 5:
            continue
        
        if is_in_distance(ny, nx, pivot_y, pivot_x):
            if board[ny][nx] != 'X' and not visited[ny][nx]:
                dfs(ny, nx, pivot_y, pivot_x, visited, board)
                
                if board[ny][nx] == 'P':
                    well_ruled = False
            
            
def is_in_distance(y, x, pivot_y, pivot_x):
    distance = abs(pivot_y - y) + abs(pivot_x - x)
    
    return True if distance <= 2 else False


def solution(places):
    global well_ruled
    
    answer = []
    for i in range(5):
        location = []
        visited = [[False for _ in range(5)] for _ in range(5)]
        well_ruled = True
        
        tmp = places[i]
        board = []
        for element in tmp:
            board.append(list(element))
        
        for j in range(5):
            for k in range(5):
                if board[j][k] == 'P':
                    location.append([j, k])
        
        for j in range(len(location)):
            y, x = location[j][0], location[j][1]
            pivot_y, pivot_x = location[j][0], location[j][1]
            
            dfs(y, x, pivot_y, pivot_x, visited, board)
            
        if well_ruled:
            answer.append(1)
        else:
            answer.append(0)
    
    return answer