🧐 문제 설명
😍 나의 풀이
거리두기를 확인하는 방법을 BFS로 어떻게 해결할 것인가?
이 문제는 겉으로 봤을 때는, 응시자가 앉아있는 자리(P)에서 맨해튼 거리가 2인 다른 P가 있는 지 체크하는 문제지만, 바꿔서 생각하면 시작점을 P로 하고 벽('X')이 아닌 지점을 방문하는 BFS 문제로 풀 수 있다. 크기가 5x5인 매트릭스로 고정이기 때문에 모두 탐색하는 방법도 시간이 얼마 안 걸리긴 할 것..
1. BFS에서 출발 지점은?
BFS를 사용하려면 경로 탐색을 시작할 출발점이 필요하다. 이 문제에서는 응시자가 앉아있는 자리(P)가 출발 지점이 된다. P는 없을 수도 있고, 여러개일 수도 있기 때문에 시작점이 되는 P의 좌표 인덱스를 모두 구해서 start 리스트에 저장한다.
한 응시자라도 거리두기 규칙을 위반했을 때 거리두기는 실패한 것이므로(return 0) 시작점들이 저장되어있는 start 리스트를 반복하며 check한다.
→ 이 때, start 리스트에 있는 P를 하나씩 BFS 하면서 거리두기 여부 check가 완료되고 나면 '방문 처리' 리스트인 visited, '경로 길이' 리스트인 distance를 모두 초기화해야 한다.
2. 빈 테이블('O'), 파티션('X')에 대한 처리는?
P는 BFS 탐색을 시작할 때 다른 P를 만나거나 모든 탐색 가능한 지점을 방문할 때까지 상하좌우 이동을 반복한다. 그렇다면 이동 가능한 위치는 어디일까?
-
탐색 중 파티션('X')를 만날 때
P가 파티션('X')을 만나면 이는 벽에 가로막힌 것으로 해당 방향으로는 탐색이 불가능하다. -
탐색 중 빈 테이블('O')을 만날 때
빈 테이블('O')은 마찬가지로 열려있는 공간이기 때문에 P가 탐색이 가능하다. -
탐색 중 또 다른 'P' 을 만날 때
P가 이동을 계속 하다가 또 다른 P를 만나면 경로 거리를 판단해서 맨해튼 거리 2보다 작으면 거리두기 실패(return 0)을 판단하고 2보다 크면 거리두기 해당 P는 거리두기 성공을 의미한다. (P가 여러 개일 수 있으니 모든 P의 시작점에서 BFS 탐색에 성공해야 return 1을 반환해야함에 주의!)
결과적으로 P의 다음 진행할 위치가 'O'이고 그 지점이 이미 방문하지 않은 곳일 때만 BFS를 진행하면 된다.
from collections import deque
def bfs(p):
start = []
for i in range(5): # 시작점이 되는 P 좌표 구하기
for j in range(5):
if p[i][j] == 'P':
start.append([i, j])
for s in start:
queue = 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 queue:
y, x = queue.popleft()
dx = [-1, 1, 0, 0] # 좌우
dy = [0, 0, -1, 1] # 상하
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<5 and 0<=ny<5 and visited[ny][nx] == 0:
if p[ny][nx] == 'O':
queue.append([ny, nx])
visited[ny][nx] = 1
distance[ny][nx] = distance[y][x] + 1
if p[ny][nx] == 'P' and distance[y][x] <= 1:
return 0
return 1
def solution(places):
answer = []
for i in places:
answer.append(bfs(i))
return answer👏 다른 사람의 풀이
출처 : Dongmin Lee님의 기록하자 벨로그
직접 이중 반복문으로 한 칸씩 다 check하는 방법을 쓰신 풀이.
def solution(places):
answer = [];
#place를 하나씩 확인
for p in places:
#거리두기가 지켜지지 않음을 확인하면 바로 반복을 멈추기 위한 key
key = False;
nowArr = [];
#이번 place를 nowArr에 담아줍니다.
for n in p:
nowArr.append(list(n));
#이중 for문을 이용해 하나씩 확인합니다.
for i in range(5):
if key:
break;
for j in range(5):
if key:
break;
#사람을 찾아내면 판단을 시작합니다.
if nowArr[i][j] == "P":
if i+1<5:
#만약 바로 아랫부분에 사람이 존재하면 break
if nowArr[i+1][j] == "P":
key = True;
break;
#만약 아랫부분이 빈테이블이고 그 다음에 바로 사람이 있다면 한칸 떨어져 있더라도 맨허튼 거리는 2이므로 break
if nowArr[i+1][j] == "O":
if i+2<5:
if nowArr[i+2][j] == "P":
key = True;
break;
#바로 오른쪽 부분에 사람이 존재하면 break
if j+1<5:
if nowArr[i][j+1] == "P":
key = True;
break;
#만약 오른쪽 부분이 빈테이블이고 그 다음에 바로 사람이 있다면 한칸 떨어져 있더라도 맨허튼 거리는 2이므로 break
if nowArr[i][j+1] == "O":
if j+2<5:
if nowArr[i][j+2] == "P":
key = True;
break;
#우측 아래 부분입니다.
if i+1<5 and j+1<5:
#만약 우측 아래가 사람이고, 오른 쪽 또는 아랫부분중 하나라도 빈테이블이면 break
if nowArr[i+1][j+1] == "P" and (nowArr[i+1][j] == "O" or nowArr[i][j+1] == "O"):
key = True;
break;
#좌측 아래부분입니다.
if i+1<5 and j-1>=0:
#만약 좌측 아래가 사람이고, 왼쪽 또는 아랫부분중 하나라도 빈테이블이면 break
if nowArr[i+1][j-1] == "P" and (nowArr[i+1][j] == "O" or nowArr[i][j-1] == "O"):
key = True;
break;
#위의 for문동안 key가 True로 변경되었다면 거리두가기 지켜지지 않은것 이므로 0을 answer에 추가
if key:
answer.append(0);
else:
#key가 false로 끝났다면 거리두기가 지켜졌으므로 1 추가
answer.append(1);
#끝!
return answer;