[프로그래머스] 거리두기 확인하기 (python) - 2021 카카오 채용연계형 인턴십

HaYeong Jang·2021년 8월 17일
0
post-thumbnail

🔗 문제링크

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

👩🏻‍💻 코드

from collections import deque

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


def bfs(place, x, y):
    visited = [[False] * 5 for _ in range(5)]
    q = deque()
    q.append((x, y, 0))
    visited[x][y] = True

    while q:
        x, y, cost = q.popleft()
        if cost == 2:
            continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < 5 and 0 <= ny < 5:
                if visited[nx][ny]:
                    continue
                if place[nx][ny] == 'P':
                    return False
                if place[nx][ny] == 'O':
                    q.append((nx, ny, cost + 1))
                    visited[nx][ny] = True
    return True


def solution(places):
    answer = []

    for place in places:
        p = [list(place[i]) for i in range(5)]	# 대기실
        flag = True

        for i in range(5):
            for j in range(5):
                if p[i][j] == 'P':
                    if not bfs(p, i, j):  # 거리두기 안 지켰을 경우
                        flag = False
            if not flag:
                break
        if flag:
            answer.append(1)
        else:
            answer.append(0)

    return answer

📝 정리

'P'인 곳에서부터 2만큼 떨어진 곳까지만 확인해 주면 되므로 BFS로 풀면 될 것이라 판단했다. 생각한 알고리즘은 아래와 같다.

  1. 대기실마다 확인하면서 'P'인 곳에서 bfs를 호출한다.
  2. bfs 내에서 좌표 및 거리 (x, y, cost)를 큐에 넣는다.
    2-1. 거리가 2 미만이고 다음 방문할 곳이 'O'라면 큐에 넣는다.
    2-2. 거리가 2 미만이고 다음 방문할 곳이 'P'라면 False를 리턴한다.
    2-3. 거리가 2 면 중지한다.
profile
기억하기 위해 기록하는 개발로그👣

1개의 댓글

comment-user-thumbnail
2022년 4월 16일

안녕하세요 몇 가지 질문이 있어 댓글 남깁니다.
1) 혹시 그냥 pop이 아닌 popleft로 한 특별한 이유가 있을까요?
2) 솔루션에 p변수로 따로 리스트를 만드셨는데 string이기 때문에 배열 형태로 다시 만들어준거죠?

답글 달기