거리두기 확인하기

접근 방법 [필수 작성]

문제이해

모든 참가자가 맨해튼거리로 서로에게 닿을 수 있는지 없는지 여부를 구하는 문제

제한 조건 확인

최대 5x5 매트릭스
P - 응시자
O - 빈테이블
X - 파티션

코너케이스

응시자가 없는 경우

아이디어

각 매트릭스에 대해서
모든 응시자를 탐색
각 응시자별로 맨해튼거리 2이내에 다른 P 가 존재하는지 BFS 탐색
X 를 만나면 q에 더 추가하지 않음

시간복잡도

최대 대기실 갯수 5대
각 대기실 크기 5x5
응시자 최대 수 25
각 응시자별 최대 bfs 탐색 횟수 4^4

→ 시간 완전 널널

코드 구현 [필수 작성]

옛날에 풀다가 포기한 코드

'''
아
시뮬레이션
백터 좌표 활용
bfs 구현
맨헤튼 거리 계산 구현

2중 포문으로 각 원소 탐색
만약 P가 나오면 bfs 시작
bfs 한칸 움직일 때마다 cnt++ 만약 bfs 시작전 cnt가 3이면 시작안하고 끝냄
bfs 하는 도중 X가 나오면 해당 가지치기 빠져나오기
bfs 하는 도중 P가 나오면 모든 bfs 중단 후 0 추가
모든 bfs 통과하면 1추가 
새로시작할때는 방문여부 체크해야함

bfs 구현은 힙큐로 가능
bfs(cnt,x,y)

시
bfs V+E
25*(4*5*2)*25 << 2억

자
bfs
방문여부체크리스트 : bool[][]

암
백시투이그
'''
import queue
    
def solution(places):
    global matrix
    
    answer = []
    
    dy = [0,1,0,-1]
    dx = [1,0,-1,0]
    
    def bfs(cnt,y,x):
        global matrix
        #print("Im Person:",y,x)
        chk = [[False]*5 for _ in range(5)]
        chk[y][x] = True
        
        q = queue.Queue()
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0<= ny <= 4 and 0 <= nx <= 4:
                #print(ny,nx)
                q.put((cnt+1,ny,nx))
        
        while q:
            #print("qsize:",q.qsize())
            c, ly, lx = q.get()
            
            if c > 2:
                continue
            case = matrix[ly][lx]
            #print("IM:",case)
            #print("x:",ly,"y:",lx)
            #print("qsize:",q.qsize())
            #print("-------------")
            if case == "P":
                if c <= 2:
                    return 0
            elif case == "X":
                pass
            elif case == "O":
                chk[ly][lx] = True
                for i in range(4):
                    ny = ly + dy[i]
                    nx = lx + dx[i]
                    if 0<= ny <= 4 and 0 <= nx <= 4:
                        if not chk[ny][nx]:
                            #print(ny,nx)
                            q.put((c+1,ny,nx))
        return 1
            
    for k in range(len(places)):
        matrix = places[k]
        rs = 1
        for j in range(len(matrix)):
            for i in range(len(matrix[j])):
                if matrix[j][i] == "P":
                    rs *= bfs(0,j,i)
        answer.append(rs)        
    
    return answer

1차 시도 (45분 소요)

한방에 통과!

BFS에 익숙해서 딱히 어렵지 않았다.

from collections import deque

def solution(places):
    answer = []
    
    dr = [1,0,-1,0]
    dc = [0,1,0,-1]
    
    listed_places = []
    #연산의 편의를 위해서 모든 string 을 리스트화 하기
    for place in places:
        tmp_place = []
        for row in place:
            tmp_rows = []
            for i in range(len(row)):
                tmp_rows.append(row[i])
            tmp_place.append(tmp_rows)
        listed_places.append(tmp_place)
    
#     for listed_place in listed_places:
#         print("-------------------------------")
#         for listed_row in listed_place:
#             print(listed_row)

    # 각 매트릭스에 대해서
    #     응시자 위치 인덱스 q에 추가, 추가하는 형식은 (r,c,count)
    #     q에 있는 모든 응시자를 탐색
    #         4가지 방향에 대해 탐색
    #             is_valid (범위내이고, 방문안했던노드고, O이면) 하면 count + 1 해서 다음 방향 추가
    #             만약 X 면 bfs 더 진행 안함
    #             만약 P 이면 (거리두기 안지키면) 바로 해당 매트릭스 bfs 탐색 종료하고 answer 에 0 추가
    
    def in_matrix(r,c):
        if 0 <= r < 5 and 0 <= c < 5:
            return True
        return False
    
    for place in listed_places:
        flag = 1 #거리두기 지킬땐 1
        for r in range(len(place)):
            if flag == 0:
                break
                
            for c in range(len(place[0])):
                if flag == 0:
                    break
                    
                if place[r][c] == "P":
                    q = deque([])
                    visited = [[False]*5 for _ in range(5)]
                    
                    q.append([r,c,0])
                    visited[r][c] = True
                    
                    while q:
                        tr,tc,count = q.popleft()
                        
                        if flag == 0:
                            break
                            
                        if count >= 2:
                            continue

                        for i in range(4):
                            nr = tr + dr[i]
                            nc = tc + dc[i]
                            if in_matrix(nr,nc) and visited[nr][nc] == False and place[nr][nc] == "O":
                                q.append([nr,nc,count+1])
                            elif in_matrix(nr,nc) and visited[nr][nc] == False and place[nr][nc] == "P":
                                flag = 0 #거리두기 안지키면 0
                                #print("현재 P:",r,c)
                                #print("거리두기 안지킨 상대 P:",nr,nc)
                                #print("현재이동거리:",count+1)
                                break
        answer.append(flag)
        
    return answer

배우게 된 점 [ 필수 X ]

해설코드

해설코드와 내 코드를 비교해보면,

객체지향프로그래밍 관점에서 함수의 명확한 구분이 되어있어 훨씬 가독성도 좋고 재사용성도 좋다.

from collections import deque

def inRange(r, c):
    return 0 <= r < 5 and 0 <= c < 5

# (r,c)로부터 맨해튼 거리 2 이하로 앉아있는 'P'가 있으면 False 반환.
# (r,c)로부터 거리유지가 다 잘되고 있으면 True 반환
def bfs(r, c, place):
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    visited = [[False] * 5 for _ in range(5)]
    q = deque()
    q.append((r, c, 0))
    visited[r][c] = True
    while q:
        cur_r, cur_c, cur_dist = q.popleft()
        for i in range(4):
            next_r = cur_r + dr[i]
            next_c = cur_c + dc[i]
            next_dist = cur_dist + 1
            if (
                inRange(next_r, next_c)
                and place[next_r][next_c] != "X"
                and not visited[next_r][next_c]
            ):
                # next distance가 2 이하를 넘어서면 건너뛴다.
                if next_dist > 2:
                    continue
                # next distance가 2 이하면서 값이 'P'면 False반환. 거리두기 실패
                if place[next_r][next_c] == "P":
                    return False

                q.append((next_r, next_c, next_dist))
                visited[next_r][next_c] = True
    return True

def check(place):
    # place 안에 있는 모든 'P'에 대해서 거리두기가 잘 되고 있는지 확인
    for r in range(5):
        for c in range(5):
            if place[r][c] == "P":
                # bfs가 False를 반환하면 이번 place는 거리두기 실패!
                if not bfs(r, c, place):
                    return False
    return True

def solution(places):
    answer = []
    for place in places:
        # 거리두기 잘 지켜지는지 확인하는 함수 => True를 반환하면 1 추가
        if check(place):
            answer.append(1)
        # 거리두기 잘 지켜지는지 확인하는 함수 => False를 반환하면 0 추가
        else:
            answer.append(0)
    return answer

질문 [ 필수 X ]

Q1

객체지향프로그래밍 관점에서 함수의 명확한 구분이 되어있어 훨씬 가독성도 좋고 재사용성도 좋다. → 문제를 빠르게 풀어야할때는 OOP 관점에서 탄탄히 설계를 하고 들어가는것이 유리할까요?(각 함수의 책임의 구분과 가독성이 좋아 길을 잃을 가능성을 줄일 수 있음) 아니면 그냥 1회성으로 빠르게 코딩하는게(속도는 빠르지만 꼬이면 망함) 더 중요할까요? 상황바이상황이겠지만, 코치님의 경험적 관점에서 어떻게 생각하시는지 궁금합니다.

피드백 [ 코치 작성 ]

사람마다 다르겠지만 저의 경우 맨 처음에 코드를 작성할 때는 함수를 분리하지 않고 코드를 작성합니다. 코드를 작성하는 도중 반복되는 로직이 발견되거나 가독성이 떨어지는 경우(ex: 너무 많은 반복, 조건문에 의해 들여쓰기가 많아진 경우) 함수를 분리해 가독성을 보완하며 코드의 재사용 측면 또한 고려합니다. 초기부터 객체지향을 고려하며 코드를 작성하면 설계에 너무 오랜 시간이 걸립니다. 문제의 풀이 방법을 생각할 때 바로 생각할 수 있는 객체지향적 측면은 고려하면서 코드를 작성하는 것이 가독성, 재사용성 등에서 도움이 되겠지만 이를 위해서 지나치게 설계를 하는 것은 비효율적이라 생각됩니다.