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

---

(처음 든 생각)

 

P가 있는 위치를 중심으로 확인하면서 넘어가려고 했다.

0~7번 자리에 P가 있으면 P 주위에 파티션이 있는지 확인

(만약 P가 아닌 O나 파티션이 있으면 일단 넘어감

어차피, P가 있으면 그 주위 탐색을 하게 될테니까?)

 

dx, dy는

위 그림의 순서처럼 선언해놨다.

 

P 주위에 또 다른 P가 대각선으로 있을때를 생각해봤다.

P1일 경우, 4,6번 방향으로 파티션이 있으면, 조건에 위배되지 않는다.

P2일 경우에는 0, 6번 방향

P3일 경우엔 0,2번 방향

P4일 경우엔 2,4번 방향

 

이렇게 조건까지 만들어서 돌렸는데 

테스트 케이스를 통과하지 전부 통과하진 못했다 +_+;

'''
거리두기 확인하기 : Programmers Level 2.
'''


def solution(places):
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, 1, 1, 1, 0, -1, -1, -1]
    button = True
    answer = []

    for array in places:
        button=True
        for i in range(5):
            for j in range(5):
                if array[i][j] == 'P':
                    for k in range(8):
                        ni = i + dx[k]
                        nj = j + dy[k]
                        if ni >= 0 and ni < 5 and nj >= 0 and nj < 5:
                            if array[ni][nj] == 'P':
                                if k == 1:
                                    # 4, 6번 확인 파티션이어야 함
                                    if array[ni + dx[4]][nj + dy[4]] == 'X' and array[ni + dx[6]][nj + dy[6]] == 'X':
                                        continue
                                    button = False
                                    break
                                if k == 3:
                                    # 0,6번
                                    if array[ni + dx[0]][nj + dy[0]] == 'X' and array[ni + dx[6]][nj + dy[6]] == 'X':
                                        continue
                                    button = False
                                    break
                                if k == 5:
                                    # 0,2번
                                    if array[ni + dx[0]][nj + dy[0]] == 'X' and array[ni + dx[2]][nj + dy[2]] == 'X':
                                        continue
                                    button = False
                                    break
                                if k == 7:
                                    # 2,4번
                                    if array[ni + dx[2]][nj + dy[2]] == 'X' and array[ni + dx[4]][nj + dy[4]] == 'X':
                                        continue
                                    button = False
                                    break
                if button is False:
                    break
            if button is False:
                break

        if button:
            answer.append(1)
        else:
            answer.append(0)

    return answer

array=[["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(array))

 

그래서 인터넷에 검색해보니..

DFS나 BFS를 쓰는것이라고 한다...?

그리고 나서 내가 했던 풀이를 다시 봤더니

좀전에 본 곳도 다시 보게 되는 아주 비효율적인 방식이었다 ;; 

왜 생각을 못했는지 ㅠ .ㅠ 

알고리즘 할 때 bfs, dfs부터 한 번 떠올리는 그런 습관을 들여놔야겟다..

빡구현만 하고 있으니 ㅠㅠ 나원참.. :(

 

---

(인터넷 풀이 참고)

https://www.youtube.com/watch?v=hCVgKE6qwFs 

** 내 코드와 다른 점! **

- 일단 bfs를 사용한다.

- dx dy도 성능 개선을 위해 튜플로 정의했다.

- queue에는 행,열, 거리를 튜플 형태로 넣는다.

 

- 거리가 1인 곳, 거리가 2인 곳을 제외한 곳은 탐색하지 않는다.

 

- 거리가 2 이하인 곳에서

- X(파티션) 만나면 continue

- O(빈테이블) 만나면 gogo

- P를 만나면 False

 

- 상하좌우만 따진 것

from collections import deque

D=((-1,0),(1,0),(0,-1),(0,1)) #상,하,좌,우 / 성능개선을 위해 튜플로 정의

def bfs(place,row,col):
    visited=[[False for _ in range(5)] for _ in range(5)]
    queue=deque()
    visited[row][col]=True
    queue.append((row,col,0)) #행,열,거리좌표
    while queue:
        now=queue.popleft()
        if now[2]>2:
            continue
        if now[2]!=0 and place[now[0]][now[1]]=='P': # 자기 자신(P)가 아닌 다른 P를 만났다.
            return False
        for i in range(4):
            nx=now[0]+D[i][0]
            ny=now[1]+D[i][1]
            if nx<0 or nx>4 or ny<0 or ny>4:
                continue
            if visited[nx][ny]:
                continue
            if place[nx][ny]=='X':
                continue
            visited[nx][ny]=True
            queue.append((nx,ny,now[2]+1))
            
    return True
    

def check(place):
    for i in range(5):
        for j in range(5):
            if place[i][j]=='P':
                if bfs(place,i,j)==False:
                    # 거리두기 지키지 x
                    return False
                
    return True
        

def solution(places):
    answer=[]
    for place in places:
        if check(place):
            answer.append(1)
        else:
            answer.append(0)
            
    return answer