[알고리즘] 거리두기 확인하기

프로그래머스 2021 카카오 채용연계형 인턴십에 출제된 문제
거리두기 확인하기 문제

---

분석

사람을 찾게되면 거리 2내의 사람이 있는지 찾기만하면 바로 규칙에 위배되므로 종료하면 된다.

place의 길이는 5이다

---

1.사람 찾기

처음부터 끝까지 한칸씩 사람이 있는지 확인하고 있으면 two() 함수로 넘어간다

---

2.칸막이 없는 부분 찾기

우선 사람의 상하좌우에 모두 칸막이가 있다면 거리 2만큼 이동할 필요가 없어지므로 칸막이가 있는지부터 체크한다. 있다면 바로 다음 사람을 찾으러 가면되고 칸막이가 없는 공간이 있다면 three() 함수로 넘어간다.

---

3.거리 2에 사람이 있는지

칸막이가 없는 칸에서 상하좌우로 이동하면 현재 사람 기준으로 거리 2만큼 이동하는게 된다. 그렇기 때문에 상하좌우 이동하며 다른 사람이 발견되는지 체크한다. 탐색 과정에서 본인은 당연히 발견되기 때문에 발견된 사람이 2명 이상이여야지 사람이 있는 것이다.

---

4. 삽질

if 0<=tmpI<5 and 0<=tmpJ<5

5부분을 생각없이 n으로 작성하여 진행과정을 하나씩 분석하며 한시간 가량을 소비하였다.

규칙에 위배되는 상황이 나오면 바로 종료해줘야 하는데 다른 place도 계산해야 되기때문에 함수로 만들어 return하여 원하는 구간에서 종료되도록 해주었다.

---

코드

dire = [[-1,0],[1,0],[0,-1],[0,1]]

def one(place): ①
    for i in range(5):
        for j in range(5):
            if place[i][j]=='P':
                if two(place,i,j)==False:  return 0
    return 1
    
def two(place,i,j): ②
    for k in range(4):
        tmpI, tmpJ = i+dire[k][0], j+dire[k][1]
        if 0<=tmpI<5 and 0<=tmpJ<5: # ④
            if place[tmpI][tmpJ]=='P': return False
            elif place[tmpI][tmpJ]=='O':
                if three(place,tmpI, tmpJ)==False: return False
    return True

def three(place,i,j): ③
    cnt=0
    for k in range(4):
        tmp2I, tmp2J = i+dire[k][0], j+dire[k][1]
        if 0<=tmp2I<5 and 0<=tmp2J<5 and place[tmp2I][tmp2J]=='P': cnt+=1
    if cnt>1: return False
    else: return True

def solution(places):
    answer = []
    for place in places: answer.append(one(place))     
    return answer