1. 5*5 의 정해진 공간 안에서 L1 distance 구하기 :
start 지점을 queue 에 append하고 bfs를 통해 각 지점에 대한 거리를 계산
2. X(칸막이 지점) : queue에다 append하지 않으면 진행되지 않는 걸 활용
from collections import deque
def bfs(place):
start = []
for i in range(5):
for j in range(5):
if place[i][j] == 'P':
start.append([i, j])
# print(start)
for s in start:
que = deque([s])
print(que)
visited = [[0] * 5 for i in range(5)]
distance = [[0] * 5 for i in range(5)]
visited[s[0]][s[1]] = 1
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while que:
y, x = que.popleft()
# print(y, x)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# print(ny,nx)
if 0 <= nx < 5 and 0 <= ny < 5 and visited[ny][nx] == 0 and place[ny][nx] != 'X':
que.append([ny, nx])
visited[ny][nx] = 1
distance[ny][nx] = distance[y][x] + 1
if place[ny][nx] == 'P' and distance[ny][nx] <= 2:
return 0
return 1
def solution(places):
answer=[]
for place in places:
answer.append(bfs(place))
return answer
places = [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]
print(solution(places))
- 제발 조급하게 굴지 말고 하나 하나 과정을 이해하자. 그게 오래 걸려도 인내심을 갖고 내 스스로가 풀이에 대해 설명할 수 있들 정도가 되어야 한다.
그 이후에 내 스스로 구현하는 건 일도 아니다.
그렇지 않고 이해도 되지 않은 상태에서 코드만 조금씩 수정하며 맞나 안맞나 확인하는 건 바보같은 짓이다.- 앞으로 정해진 공간 안에 거리계산하는 문제가 나온다면, bfs를 떠올려 보자.
def check(place):
for irow, row in enumerate(place):
for icol, cell in enumerate(row):
if cell != 'P':
continue
if irow != 4 and place[irow + 1][icol] == 'P':
return 0
if icol != 4 and place[irow][icol + 1] == 'P':
return 0
if irow < 3 and place[irow + 2][icol] == 'P' and place[irow + 1][icol] != 'X':
return 0
if icol < 3 and place[irow][icol + 2] == 'P' and place[irow][icol + 1] != 'X':
return 0
if irow != 4 and icol != 4 and place[irow + 1][icol + 1] == 'P' and (place[irow + 1][icol] != 'X' or place[irow][icol + 1] != 'X'):
return 0
if irow != 4 and icol != 0 and place[irow + 1][icol - 1] == 'P' and (place[irow + 1][icol] != 'X' or place[irow][icol - 1] != 'X'):
return 0
return 1
def solution(places):
return [check(place) for place in places]