https://programmers.co.kr/learn/courses/30/lessons/81302?language=python3
1. 해설
아래와 같은 로직을 구현하면 된다.
1. 지원자들의 위치를 담고 있는 리스트를 만든다.(loc_p)
2. 그 리스트로부터 중복없이 2명을 뽑아 이 두명이 적절한 거리두기를 하고 있는지 확인한다.
3. 거리두기 로직은 다음과 같다.
1. BFS로 탐색하지 못하면 => 거리두기 만족(True)
2. BFS로 탐색 가능하지만 두 사람의 맨해튼 거리가 2 이상이면 거리두기 만족(True)
3. 위 두조건이 아니면 False
4. 모든 쌍에 대해서 True라면 해당 대기장소는 True 아니면 False
약간 까다로운 점은 맨해튼 거리를 매번 구해주는게 아니라 visited 리스트에 저장해서 사용하는 점과 BFS 탐색시 다른 지원자를 만났을 때 어떻게 해야하는지였다.
def bfs(start, target, place):
"""
start로 부터 target가 서로 거리두기를 하는지 확인하는 함수
BFS로 탐색하면서 start가 target에 도착 불가능하면 => True
도착해도 맨해튼 거리가 2 이상이라면 => True
둘다 아니면 => False
맨해튼 거리는 따로 계산하지 않고 visited에 저장해서 사용했다.
"""
# 초기화 부분
N=5
q = [start]
visited = [[-1 for i in range(N)] for i in range(N)]
visited[start[0]][start[1]] = 0
moves =[[1,0],[0,1],[0,-1],[-1,0]]
#q가 빌 때까지
while q:
r, c = q.pop(0)
#만약 현재 위치가 찾던 위치라면
if (r,c) == target:
if visited[r][c] > 2: #시작지점에서 맨해튼 거리를 visited에서 확인 후 2 초과라면
return True
return False
#상하 좌우로 움직임
for dr, dc in moves:
nr, nc = r+dr, c+dc
#place를 벗어나면 다시 계산
if nr <0 or nr >= N or nc < 0 or nc >= N or place[nr][nc] == "X":
continue
#방문하지 않았다면
if visited[nr][nc] == -1:
#시작점으로부터 거리를 업데이트하고
visited[nr][nc] = visited[r][c] + 1
#큐에 넣어준다.
q.append((nr, nc,))
#target에 도착하지 못했다면 거리두기를 잘하고 있음으로 True 반환
return True
def is_proper_distance(place):
""" 적절한 거리두기를 하고 있는지 확인하는 함수"""
N = len(place)
loc_p = []
#대기 장소를 돌면서 지원자들의 위치를 확인한다.
for i in range(N):
for j in range(N):
if place[i][j] == "P":
loc_p.append((i,j,))
#지원자들 리스트에서 중복없이 2개를 뽑는다.
for i in range(len(loc_p)):
for j in range(i+1, len(loc_p)):
start, target = loc_p[i], loc_p[j]
#거리 두기 조건을 확인한다.
isContent = bfs(start, target, place)
#만족하지 못했다면 False 반환
if not isContent:
return False
# 모든 쌍에 대해 만족했다면 True 반환
return True
def solution(places):
answer = []
for place in places:
#해당 장소가 적절한 거리두기를 확인해서
result=is_proper_distance(place)
if result: # 결과가 참이면 1을 넣고
answer.append(1)
else: #아니면 0을 넣는다
answer.append(0)
return answer
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스] SQL 입양시간 구하기(2) (0) | 2021.07.16 |
---|---|
[프로그래머스, 2021 카카오 인턴쉽] 표 편집 python (0) | 2021.07.13 |
[프로그래머스] 광고 삽입 python (2021 Kakao Blind Test) (0) | 2021.06.16 |
프로그래머스 동굴 탐험 python (0) | 2021.06.06 |
프로그래머스 트리 트리오 python (0) | 2021.06.06 |