2021 KAKAO INTERNSHIP 거리두기 확인하기 파이썬

2021 KAKAO INTERNSHIP 거리두기 확인하기 파이썬 풀이

바로 이전에 풀었던 튜플 문제와 동일한 2레벨 문제입니다.

1시간의 풀이 이후 while문을 탈출하지 못하는 오류를 해결하지 못했습니다.
**이전의 구현문제나 DFS 문제처럼 deque을 이용하여 좌표를 계속 이동시켜주면서
탐색을 하면 되는 것은 알았으나, 정답 코드를 작성하지 못하여 sem.log님의 블로그를 참고했습니다.

오답코드

from collections import deque

def solution(places):
    # 거리두기 1 / 0
    # 동북서남
    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]
    answer = []
    for i in range(5):
        # 일시적으로 대기실을 만들어 저장
        room = []
        for j in range(5):
            room.append(list(places[i][j]))
            # 여기서부터 구현 진행
        q = deque()
        for a in range(5):
            for b in range(5):
                if room[a][b] == "P":
                    print("a", a, "b", b)
                    q.append((a, b))
                    while q:
                        dist = 0
                        x, y = q.popleft()
                        for t in range(4):
                            nr = x + dr[t]
                            nc = y + dc[t]
                            dist += 1
                            # 경우의 수:
                            '''
                            1. 이동하면서 범위를 넘으면 안됨
                                2. 거리를 계속 누적시켜야함
                                3. 이동할 때 마주치는 경우의 수는 3가지.
                                    - P를 만날 때 : 거리가 2 이하일 경우엔 0을 append하고 while문 break / 나머지는 pass
                                    - X를 만날 때 : 거리를 0으로 초기화
                                    - O를 만날 때 : 계속 패스
                            '''
                            if 0 <= nr < 5 and  0 <= nc < 5:
                                if room[nr][nc] == "P" and dist <= 2:
                                    answer.append(0)
                                    break
                                elif room[nr][nc] == "X":
                                    q.append((nr, nc))
                                    dist = 0
                                else:
                                    q.append((nr, nc))
                                    dist += 1


    return answer

접근방식

1. 우선 P가 있는 좌표를 시작으로 주변을 탐색합니다.
2. P가 있는 좌표를 큐에 append 시켜줍니다.
3. 이후 dr, dc를 통해 좌표를 상하좌우로 이동시켜줍니다.
4. 이동한 좌표가 방문했거나 범위를 넘어가지 않도록 if문을 지정해줍니다
5. 이동한 좌표가 O일 경우, 거리를 1 증가시켜주고, 방문처리해줍니다.
6. 만약 P이고 이전까지 거리가 1이하일 경우, 바로 0을 return 시켜줍니다.

정답코드

from collections import deque

def bfs(p):
        p_list = []
        for a in range(5):
            for b in range(5):
                if p[a][b] == "P":
                    p_list.append([a, b])

        for s in p_list:
            q = deque([s])
            visited = [[0]*5 for i in range(5)]
            distance = [[0] * 5 for i in range(5)]
            visited[s[0]][s[1]] = 1
            while q:
                x, y = q.popleft()
                # 동북서남
                dr = [-1, 0, 1, 0]
                dc = [0, 1, 0, -1]
                for t in range(4):
                    nr = x + dr[t]
                    nc = y + dc[t]
                    if 0 <= nr < 5 and 0 <= nc < 5 and visited[nr][nc] == 0:
                        if p[nr][nc] == "O":
                            q.append([nr,nc])
                            visited[nr][nc] = 1
                            distance[nr][nc] = distance[x][y] + 1
                        if p[nr][nc] == "P" and distance[x][y] <= 1:
                            return 0
        return 1

def solution(places):
    answer = []

    for i in places:
        answer.append(bfs(i))
    return answer

이번 문제를 통해 새롭게 알게 된 것은,

좌표를 탐색해야 하는 알고리즘에서 visited 리스트와 거리를 구해야 하는 distance 리스트의

존재가 필수적이라는 것과 return 값에 0과 1 값을 넣어서 이후 for문을 통해

자연스럽게 answer 리스트에 함수 자체를 append 시키면 값을 넣을 수 있는 작동 원리입니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady