[프로그래머스] 거리두기 확인하기

def dfs(place, x, y, distance, visited):
    distance = distance + 1
    visited[x][y] = 1
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    if distance > 2:
        return True
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= 5 or ny < 0 or ny >= 5:
                continue
            elif visited[nx][ny] == 0:
                if place[nx][ny] == 'P':
                    return False
                elif place[x+dx[i]][y+dy[i]] == 'X':
                    continue
                elif place[x+dx[i]][y+dy[i]] == 'O':
                    
                    if dfs(place, nx, ny, distance, visited) == False:
                        return False
        return True
                
def solution(places):
    answer = [1, 1, 1, 1, 1]
    for idx, place in enumerate(places):
        visited = [[0 for _ in range(5)] for _ in range(5)]
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    if dfs(place, i, j, 0, visited) == False:
                        answer[idx] = 0
                        break
            
    return answer

1. DFS 풀이

• P인 곳에서 매번 dfs함수를 실행한다.
• dfs의 return은, 선택된 P를 기준으로 거리두기를 지키고 있으면 True를, 거리두기를 지키지 않고 있으면 False를 return한다.
• dfs함수 안에서는,
  • distance가 2를 넘어가면 더이상 탐색을 멈춘다(return True). 거리가 2가 넘었는데도 return False에 한 번 도 걸리지 않았다면 이 경우는 거리두기를 잘 지키고 있는 것이라고 할 수 있다.
  • distance가 2이하일 때, 사방으로 이동하다가 P를 만나면 return False
  • distance가 2이하일 때, 사방으로 이동하다가 X를 만나면 막힌 셈 치고 continue (아무런 영향 x)
  • distance가 2이하일 때, 사방으로 이동하다가 O를 만나면 dfs 재귀 호출

알고 보면 어렵지 않은 문제인데 뭘 그렇게 헤맸는지...

 

from collections import deque
def bfs(place):
    start = []
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P':
                start.append([i, j])

    for i in start:
        queue = deque([i])
        visited = [[0 for _ in range(5)] for _ in range(5)]
        distance = [[0 for _ in range(5)] for _ in range(5)]
        visited[i[0]][i[1]] = 1
        while queue:
            x, y = queue.popleft()
            
            dx = [-1, 1, 0, 0]
            dy = [0, 0, -1, 1]
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < 5 and 0 <= ny < 5 and visited[nx][ny] == 0:
                    if place[nx][ny] == 'P' and distance[x][y] < 2:
                        return 0
                    elif place[nx][ny] == 'O':
                        queue.append([nx, ny])
                        distance[nx][ny] = distance[x][y] + 1
                        visited[nx][ny] = 1
    return 1
                        
                        
            
def solution(places):
    answer = [1, 1, 1, 1, 1]
    for idx, place in enumerate(places):
        answer[idx] = bfs(place)
            
        
    return answer

2. BFS 풀이

음. 나는 머리로는 BFS가 더 나은 풀이라고 생각하는데 구현을 잘 못하겠어서 DFS로 풀었다.

이 풀이는 다른 사람의 풀이를 참고한 것이다.