기본적으로 BFS의 개념과 파이썬에서 사용하는 데크의 개념을 알고있어야 풀 수 있는 문제였다. 나는 두가지 다 제대로 몰랐기 때문에 못품 ;;
답안을 봐도 한번에 이해하기 힘들었다. 이거 레벨2 맞나...? 또르르... 아무튼 다른 블로그에서 보면서 코드를 이해한 내용을 바탕으로 문제 풀이를 해볼 예정이다.
일단 문제풀이를 하기 전에 BFS와 파이썬의 데크 개념을 정리할 것이다.
1. BFS
너비 우선 탐색이다. 문제를 풀 때 이 문제가 BFS다 라고 생각이 들면, BFS를 적용할 줄 알아야한다. 이번 문제도 동일한 부류인데, 과연 내가 실제 문제 풀이에서 이런 로직을 적용할 수 있을지는 모르겠다. 아무튼 BFS 개념을 정리한다.
1. 트리로 그려보자
BFS든, DFS든 트리를 그려서 풀이하는게 좀 더 이해에 도움이 된다. 다음 하단의 트리를 확인해보자.
여기서 BFS는 말 그대로 너비우선 탐색이다. 너비를 레벨이라고 바꿔서 생각해보자.
오른쪽의 숫자를 레벨이라고 생각하면, 1-2-3-4 의 레벨 순으로 탐색이 된다. 말 그대로 이다. 어렵게 생각할수록 알고리즘은 괴로워진다.
이제 말 그대로 레벨 순서대로 탐색을 해보자.
먼저 레벨1 탐색
탐색 끝
레벨 2 탐색
레벨 2 탐색 끝
레벨 3 탐색
레벨 3 탐색 끝
레벨 4 탐색
이렇게 된다.
이것을 짧은 영상으로 상세하게 보면 다음과 같다.
2. 사용하는 자료구조
- 위의 영상에서 보면, 노드를 집어넣고 들어온 순서대로 제거해야 한다. 이때 쓰이는건 FIFO이다. 즉, 큐를 사용해야 한다. 파이썬에서 FIFO큐를 사용하려면 deque를 사용해야한다.
from collections import deque
deque_test = deque()
deque_test.append(a) # a를 데크의 오른쪽 끝에 삽입한다.
deque_test.appendleft(a) # a를 데크의 왼쪽 끝에 삽입한다.
deque_test.pop() # 데크의 맨 오른쪽 엘리먼트를 가져오는 동시에 삭제한다.
deque_test.popleft() # 데크의 맨 왼쪽 엘리먼트를 가져오는 동시에 삭제한다.
deque_test.extend(array) # 배열 array를 순환하면서 데크의 오른쪽에 추가.
deque_test.extendleft(array) # 배열 array를 순환하면서 데크의 왼쪽에 추가.
deque_test.remove(a) # 데크에서 a원소를 찾아서 삭제한다.
deque_test.rotate(n) # 데크를 n만큼 회전시킨다.데크는 위와 같은 여러가지 메소드가 있는데, 여기서 FIFO와 관련된 메소드는 append와 popleft이다.
- set() 이번 문제에서는 사용되지 않았지만, 혹은 사용하지 않을 수도 있지만 가끔 사용한다.
위의 gif그림을 보면 한번 방문한 노드는 다시 방문하지 않는다. 왜냐면 이미 탐색했기 때문에 방문할 필요가 없기 때문이다. 그래서 set을 사용할 경우가 있다. 이번문제에서는 사용하지 않았다.
2. 문제 풀이
from collections import deque
d = ((0, 1), (1, 0), (-1, 0), (0, -1))
SIZE = 5
def make_maps(place):
arr = []
men = []
for i, string in enumerate(place):
for j, ch in enumerate(string):
if ch == 'P': men.append((i, j))
arr.append(list(string))
return arr, men
def isin(y, x): # 전체 5*5 배열에 들어오는지 확인
if -1 < y < SIZE and -1 < x < SIZE: return True
return False
def bfs(arr, sy, sx):
q = deque()
q.append((sy, sx)) # 큐에 받은 P점의 좌표를 집어넣기
table = [[-1 for _ in range(SIZE)] for _ in range(SIZE)]
table[sy][sx] = 0 # 그 위치를 제외한 나머지 5*5 배열 -1, 그 위치는 0으로 설정
while q:
y, x = q.popleft() # q에서 하나를 꺼낸다. (가장 앞쪽에서 꺼내는 것)
for dy, dx in d: # d는 q점에서 상하좌우 인 곳
ny = y + dy # 각각 상하 좌우를 확인한다.
nx = x + dx
if not isin(ny, nx): continue # 5*5 배열에 들어오는지 확인하고 없으면 패스
if arr[ny][nx] != 'X' and table[ny][nx] == -1: # 파티션이 아니고, 아직 방문을 안한 점
table[ny][nx] = table[y][x] + 1 # 원래 점에서 1만큼 떨어져있음으로, 거리 1을 더해준다.
# 아 그러니까 원래 점을 기준으로 BFS를 돌기 때문에 원래 점 기준으로 그 다음점은 +2가 되겠다.
q.append((ny, nx)) # 큐에 집어넣는다.
return table
def solution(places):
answer = []
for place in places:
arr, men = make_maps(place)
ok = True
for man in men:
table = bfs(arr, man[0], man[1]) # P점의 좌표를 인자로 받음(1개씩)
for other_man in men:
if man != other_man: # 다시 P점들 중 하나를 뽑고, 기존에 비교하려던 점과 같지 않으면
y = other_man[0] #그것을 x,y에 넣는다.
x = other_man[1]
if -1 < table[y][x] <= 2: # 그리고, 위에서 bfs를 돌아서 거리두기 성립이 안되면
ok = False # 폴스로 설정해둠
break
if not ok: break # 그래서, 해당 P점이 다른 P점과 거리두기가 아니면 break
if ok:
answer.append(1)
else:
answer.append(0)
return answer1. 하나의 점을 기준으로 다른 점과의 거리 두기 관계를 확인한다.
풀이 방법을 요약하자면 다음과 같다.
-
make_maps(place): P가 있는 즉, 사용자가 앉아있는 모든 좌표를 확인하여 men으로 리턴한다. 그리고 arr에는 [['P', 'O', 'O', 'O', 'P'], ['O', 'X', 'X', 'O', 'X'], ['O', 'P', 'X', 'P', 'X'], ['O', 'O', 'X', 'O', 'X'], ['P', 'O', 'X', 'X', 'P']] 이런 식으로 하나의 대기실에 대해 2차원 배열로 변환해서 리턴한다.
-
isin(y, x): 확인하려는 점이 5*5 배열에 속해있는지를 확인한다.
-
bfs(arr, sy, sx) : 이 함수를 해석하는 것이 매우 어려웠는데, 이 문제에서는 사용자와 사용자 사이의 거리를 확인해야 한다. 따라서 어떤 p의 좌표가 주어졌을 때 해당 P의 좌표를 기준으로 떨어져있는 모든 점의 거리를 탐색한 결과를 배열로 ret해주는 것이다. 다시말하지만 P좌표만 기준으로 한다. 다른 점 기준으로 거리두기 결과는 다시 bfs를 돌려서 확인해야한다.
그림으로 한번에 설명하자면 다음과 같다.
다음과 같은 전체 배열의 일부분이 있다고 가정하자. 나는 가장 가운데 점인 P점을 기준으로 bfs 함수를 실행해보려고 한다.
초기 세팅은 다음과 같아질 것이다.
첫번째 P점을 꺼내고, 순서대로 상하좌우 점을 확인한다. 여기서arr[ny][nx] != 'X' and table[ny][nx] == -1조건에 걸리는 점은 중심점+1 값으로 업데이트 된다.
위의 점도 마찬가지로 업데이트 된다.
상하좌우를 모두 확인했다면, 상하좌우 점 자체를 큐에 다시 집어넣고 순서대로 탐색한다.
현재는 동그라미 표시된 점을 기준으로 상하좌우를 탐색하게 되고, 기존에 업데이트 되었던 가중치에 +1이 업데이트 된다.
즉, 초기P점을 기준으로 +1이 가중되어 P점을 기준으로 한 거리두기 결과가 나오게 되는 것이다.
이렇게 거리두기 결과를 확인하고, 이를 다른 P점과 확인해서 거리가 2 이하가 되면 거리두기를 충족하지 않아 break되는 방식이다.2. 이해했으니, 답변을 안보고 풀어보자.
풀이 방식을 이해하고, 어느정도 머리에 담아둔 후 풀어보았다.
결과는 몇가지 주의사항을 제외하고 통과했다. -
P점을 기준으로 거리 두기 테이블을 계산할 때 최초에 P점의 거리를 0으로 설정해야 한다. 이때 내가 P점을 큐에 집어넣었는데 집어 넣고 0으로 초기화 해버렸다. while문을 돌아야 하는데 말이다... 함수 진입시 초기화 해야한다. while문을 도는 부분은 큐에서 pop하고, 상하좌우 점들을 비교하면서 거리의 가중치를 더하는 부분이다.
-
for문이 여러개 중첩되어있어서 한번에 for문을 빠져나오는 방법이 헷갈렸다. 이런 방법이 있다.
for ~
for ~:
is_true = true
for ~:
is_true = false
break
if not is_true:
break