[코딩테스트]프로그래머스 - 거리두기(카카오 2021 blind recruitment)

문제 풀기
나의 풀이

Key ideation

1. 5*5 의 정해진 공간 안에서 L1 distance 구하기 :
start 지점을 queue 에 append하고 bfs를 통해 각 지점에 대한 거리를 계산
2. X(칸막이 지점) : queue에다 append하지 않으면 진행되지 않는 걸 활용

🤡풀이

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])
    # print(start)

    for s in start:
        que = deque([s])
        print(que)
        visited = [[0] * 5 for i in range(5)]
        distance = [[0] * 5 for i in range(5)]
        visited[s[0]][s[1]] = 1

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

        while que:
            y, x = que.popleft()
            # print(y, x)
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                # print(ny,nx)
                if 0 <= nx < 5 and 0 <= ny < 5 and visited[ny][nx] == 0 and place[ny][nx] != 'X':
                    que.append([ny, nx])
                    visited[ny][nx] = 1
                    distance[ny][nx] = distance[y][x] + 1
                    if place[ny][nx] == 'P' and distance[ny][nx] <= 2:
                        return 0

    return 1

def solution(places):
    answer=[]
    for place in places:
        answer.append(bfs(place))
    return answer


places = [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]



print(solution(places))

회고

• 제발 조급하게 굴지 말고 하나 하나 과정을 이해하자. 그게 오래 걸려도 인내심을 갖고 내 스스로가 풀이에 대해 설명할 수 있들 정도가 되어야 한다.
  그 이후에 내 스스로 구현하는 건 일도 아니다.
  그렇지 않고 이해도 되지 않은 상태에서 코드만 조금씩 수정하며 맞나 안맞나 확인하는 건 바보같은 짓이다.
• 앞으로 정해진 공간 안에 거리계산하는 문제가 나온다면, bfs를 떠올려 보자.

참고

• 거리가 2 이내라는 조건이 달려 있어서, 가능한 경우의 수를 모두 나열한 풀이.

def check(place):
    for irow, row in enumerate(place):
        for icol, cell in enumerate(row):
            if cell != 'P':
                continue
            if irow != 4 and place[irow + 1][icol] == 'P':
                return 0
            if icol != 4 and place[irow][icol + 1] == 'P':
                return 0
            if irow < 3 and place[irow + 2][icol] == 'P' and place[irow + 1][icol] != 'X':
                return 0
            if icol < 3 and place[irow][icol + 2] == 'P' and place[irow][icol + 1] != 'X':
                return 0
            if irow != 4 and icol != 4 and place[irow + 1][icol + 1] == 'P' and (place[irow + 1][icol] != 'X' or place[irow][icol + 1] != 'X'):
                return 0
            if irow != 4 and icol != 0 and place[irow + 1][icol - 1] == 'P' and (place[irow + 1][icol] != 'X' or place[irow][icol - 1] != 'X'):
                return 0
    return 1

def solution(places):
    return [check(place) for place in places]