[프로그래머스 LV.2] 거리두기 확인하기(파이썬 / python)

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

코딩테스트 연습 - 거리두기 확인하기

 

만약 참가자 p 자리가 있을때

p를 기준으로 bfs를 뎁스가 2일때까지 돌려준다.

 

파란색은 뎁스가1일때, 거리가 1이고

빨간색은 뎁스가2일때, 거리가 2이다.

 

p를 기준으로 직선에 P가 있을경우 가운데 X 가 있으면 거리두기를 제대로 수행한것이며

P를 기준으로 대각선에 P가 있을경우 그 사이에 X가 둘 다 있어야 거리두기를 제대로 수행한것이다.

 

 

from queue import Queue
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
 
# type이 0 이면 직선거리, type이 1이면 대각선
def check(i, j, nx, ny, type, place):
    # 직선상태
    if type == 0:
        if i == nx:
            if place[i][(j + ny) // 2] == "X":
                return True
            else:
                return False
        elif j == ny:
            if place[(i + nx) // 2][j] == "X":
                return True
            else:
                return False
    # 대각선
    elif type == 1:
        if place[i][ny] == "X" and place[nx][j] == "X":
            return True
        else:
            return False
 
 
def bfs(i, j, place):
    q = Queue()
 
    q.put([i, j])
    visit = [[0 for a in range(5)] for b in range(5)]
 
    visit[i][j] = 1
 
    while not q.empty():
 
        v = q.get()
 
        for a in range(4):
 
            nx = v[0] + dx[a]
            ny = v[1] + dy[a]
 
            if 0 <= nx < 5 and 0 <= ny < 5 and visit[nx][ny] == 0:
 
                if place[nx][ny] == "P":
 
                    # 직선상태
                    if i == nx or j == ny:
                        result = check(i, j, nx, ny, 0, place)
                    # 대각선상태
                    else:
                        result = check(i, j, nx, ny, 1, place)
                    # print(i, j, nx, ny, result, place[nx][ny])
 
                    if result is False:
                        return False
 
                visit[nx][ny] = visit[v[0]][v[1]] + 1
                print(visit[nx][ny])
                if visit[nx][ny] <= 2:
                    q.put([nx, ny])
                    print(visit)
 
    return True
 
 
def solution(places):
    answer = []
    for p in places:
        result = True
 
        for i in range(5):
            for j in range(5):
 
                if p[i][j] == "P":
 
                    result = bfs(i, j, p)
 
                    # 거리두기 안 지킨 사람이 존재할시 반복문 중단하고 0반환환
                    if result is False:
                        answer.append(0)
                        break
            if result is False:
                break
        if result is True:
            answer.append(1)
 
    return answer