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

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

프로그래머스

문제 개요

 

<Input>

 

Places: ‘자리에 앉아있는 응시자들의 정보와 대기실 구조’를 대기실별로 담은 2차원 문자열 배열.

*대기실은 5개이며, 각 대기실은 5x5 크기

*P(응시자가 앉아있는 자리),O(빈 테이블),X(파티션)로 이루어진 문자열

*Rule

1. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
2. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

예: [["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"]]

 

<Output>

 

각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아.

예: [1, 0, 1, 1, 1]

 

 

내 코드

못생긴 코드ㅡ... 코드가 왜 이렇게 길지? ^__^

ㅎㅎ

모범코드 보면서 공부해야겠다..

from collections import deque
def solution(places):
    
    answer = [1 for _ in range(5)]

    next_i, next_j = [-1, 0, 0, 1], [0, -1, 1, 0]
    doub_i, doub_j = [-2, 0, 0, 2], [0, -2, 2, 0]
    cross_i, cross_j = [-1, -1, 1, 1], [-1, 1, -1, 1]

    cnt = -1
      
    for place in places:
        cnt += 1
        place = list(map(list, place))
        p_lst = deque() #각 대기실에서 P가 있는 좌표 리스트
        for i, row in enumerate(place):
            for j, col in enumerate(row):
                if place[i][j] == 'P':
                    p_lst.append((i,j))
                    
        loopbreak = False
        while p_lst and (loopbreak == False):
            (i,j) = p_lst.popleft() #현재 중심이 되는 좌표 (i,j)
            for k in range(4): #위반 케이스 1
                ci = i + next_i[k]
                cj = j + next_j[k]
                
                if ci <0 or ci>4 or cj<0 or cj>4:
                    continue
                if place[ci][cj] == 'P':
                    answer[cnt] = 0
                    loopbreak = True
                    break
                
            if loopbreak == True: break
            for k in range(4): #위반 케이스 2
                ci = i + doub_i[k]
                cj = j + doub_j[k]
                if ci <0 or ci>4 or cj<0 or cj>4:
                    continue
                if place[ci][cj] == 'P':
                    if place[i + next_i[k]][j + next_j[k]] == "O":
                        answer[cnt] = 0
                        loopbreak = True
                        break
            if loopbreak == True: break
            for k in range(4): #위반 케이스 3
                ci = i + cross_i[k]
                cj = j + cross_j[k]
                if ci <0 or ci>4 or cj<0 or cj>4:
                    continue
                if place[ci][cj] == 'P':
                    if k == 0:
                        if place[i-1][j]=='X' and place[i][j-1]=='X': continue   
                    elif k == 1:
                        if place[i-1][j]=='X' and place[i][j+1]=='X': continue  
                    elif k == 2:
                        if place[i][j-1]=='X' and place[i+1][j]=='X': continue
                    elif k == 3:
                        if place[i][j+1]=='X' and place[i+1][j]=='X': continue
                    
                    answer[cnt] = 0
                    loopbreak = True
                    break

    return(answer)

 

• 테케 3, 8, 31번 오답의 반례 : 'POP'가 포함된 경우 '0'을 반환해야 한다
• answer의 default 원소로 1 채워놓고, 위반하는 경우=>  0으로 바꿈 & 다음 place로 바로 이동(기존 반복문 break)
• visited 리스트 이용해서 좀 더 효율적으로 구현했었는데 => 딱히 효과가 없다 ^__^ BFS 개념에 집착하지 말자,,

 

• 이중 반복문 빠져나오는 법: loopbreak과 같은 변수 사용,,
• 반복문 continue 개념

https://velog.io/@banana/break-continue%EB%A1%9C-%EB%B0%98%EB%B3%B5%EB%AC%B8-%EC%A0%9C%EC%96%B4%ED%95%98%EA%B8%B0

break, continue로 반복문 제어하기

• 상하좌우 살피는 예쁜 코드 [-1,0,0,1] 등 사용해서 짰는데 (왜 전체 코드가 이리 장황할까?)

그래도 아래 코드는 유용하게 사용하쟈~

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

for k in range(4):
            cx = i + dx[k]
            cy = j + dy[k]
            if cx < 0 or cx >= N or cy < 0 or cy >= M:
                continue
            if arr[cx][cy] != 1:
                graph[i*M+j].append(cx*M+cy)