[2021 카카오 채용연계형 인턴십 / 프로그래머스] 81302번: 거리두기 확인하기 (다시)

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

 

Lv2 문제다! bfs인 것 같은데 대각선에 있는 경우는 어떻게 처리해야할지 모르겠어서 일반 구현으로 풀었는데 테스트 하나에서 자꾸 틀려서 구글링 했다 

 

풀이 로직 

• places의 각 원소들을 탐색하다가 P를 만나면 해당 위치를 기준으로 bfs를 돌린다 
• bfs에서는 범위 내에서 상, 하, 좌, 우에 있는 원소 중 
  • 맨하탄 거리가 2이하이고, 방문하지 않았는데 P인 경우 false를 반환하고
  • 맨하탄 거리가 2이하이고, 방문하지 않았는데 O인 경우 bfs를 이어나간다 
• while문을 빠져나왔다는 것은 중간에 False를 한번도 만나지 않은 것이므로 True를 반환한다 

 

- 정답 풀이 :

 

특정 P마다 모두 확인해야하므로 bfs 안에 visit를 생성하는 것 같고 

시작한 P의 위치(sx,sy)에서 반경 2 안에 있는 것들에 대해서 탐색해야하므로 abs(nx - sx) + abs(ny - sy) <= 2가 되는 것 같고

 

탐색하다가 반경 내에서 P를 만나면 안되고

반경 내에서 O인 경우에만 이동할 수 있다 

----> 위 두줄만 이해가 안 간다 

 

참고한 블로그

from collections import deque

def bfs(places, sx, sy):
    queue = deque([(sx, sy)])
    
    visit = [[0] * 5 for _ in range(5)]
    
    dx = [1, -1, 0, 0]
    dy = [0, 0 , 1, -1]
    visit[sx][sy] = 1
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < 5 and 0 <= ny < 5 and (abs(nx - sx) + abs(ny - sy) <= 2) and not visit[nx][ny]:
                if places[nx][ny] == 'P':
                    return False
                if places[nx][ny] == 'O':
                    visit[nx][ny] = 1
                    queue.append((nx,ny))
    return True
    
def solution(places):
    answer = [1] * 5
    
    for t in range(5):
        for i in range(5):
            for j in range(5):
                if places[t][i][j] == 'P':
                    if not bfs(places[t], i, j):
                        answer[t] = 0
                        break
                        
                        
    return answer

 

 

- 시도해 본 풀이 :

30 / 31 테스트 통과한 풀이인데, 한 문제가 계속 틀린다.

edge case에 대한 처리가 부족한건가 싶은데 아직은 잘 모르겠다 

 

풀이 로직

• P의 위치를 location에 저장한다 ([i, j] 형태로)
• 맨하탄 거리를 안 지키는 두 P의 위치를 하나의 배열로 만들어 manhattan에 저장한다 
• manhattan에 있는 P중에서 거리두기를 지키는 경우 count로 센다
• 만약 manhattan에 있는 모든 쌍들이 거리두기를 지킬 경우 count와 len(manhattan)이 같기에 1을 반환하고,
• 아니라면 0을 반환한다
• places의 모든 행렬에 대해 위 과정을 반복한다 

 

거리두기가 허용되는 경우 

 

 

def distance(place):
    n, m = len(place), len(place[0])
    
    location = []
    for i in range(n):
        for j in range(m):
            if place[i][j] == 'P':
                location.append([i, j])
                
    location.sort()
    manhatan = []
    for i in range(len(location)):
        for j in range(i + 1, len(location)):
            x = abs(location[i][0] - location[j][0])
            y = abs(location[i][1] - location[j][1])
            if x + y <= 2:
                manhatan.append([location[i], location[j]])
                
    count = 0         
    for i in range(len(manhatan)):
        first, second = manhatan[i]
        
        if first[0] == second[0]:
            if place[first[0]][first[1] + 1] == 'X':
                count += 1
        elif first[0] + 2 == second[0]:
            if first[1] == second[1]:
                if place[first[0] + 1][first[1]] == 'X':
                    count += 1
        elif first[0] + 1 == second[0]:
            if first[1] + 1 == second[1]:
                if place[first[0]][first[1] + 1] == 'X':
                    if place[first[0] + 1][first[1]] in ['X', 'O']:
                        count += 1
                elif place[first[0]][first[1] + 1] == 'O':
                    if place[first[0] + 1][first[1]] == 'X':
                        count += 1
            elif first[1] == second[1] + 1:
                if place[first[0]][second[1]] == 'X' and place[second[0]][first[1]] == 'X':
                    count += 1
                    
    if count == len(manhatan):
        return 1
    else:
        return 0
    
    
def solution(places):
    
    answer = []
    for i in range(len(places)):
        answer.append(distance(places[i]))
        
    return answer