(프로그래머스 with python) 거리두기 확인하기
Level2 - 거리두기 확인하기
https://programmers.co.kr/learn/courses/30/lessons/81302
처음 풀었던 풀이다. 14.9 / 100 으로 대부분의 테스트케이스 통과를 하지 못했다
# 합계: 14.9 / 100.0
from collections import deque
def bfs(places, x, y):
res = 1
visited = [[0] * len(places) for _ in range(len(places))]
dx = [-1, 1, 0, 0] # 상하좌우
dy = [0, 0, -1, 1]
visited[x][y] = 1
queue = deque()
queue.append([x, y])
while queue:
x, y = queue.popleft()
for i in range(4):
xx = x + dx[i]
yy = y + dy[i]
if places[x][y] == 'P':
if 0 <= xx < 5 and 0 <= yy < 5 and not visited[xx][yy]:
visited[xx][yy] = 1
if places[xx][yy] == 'O':
if dx[i] == -1: # 상
if xx > 0:
if places[xx - 1][yy] == 'P':
res = 0
break
elif dx[i] == 1: # 하
if xx < 4:
if places[xx + 1][yy] == 'P':
res = 0
break
elif dy[i] == -1: # 좌
if yy > 0:
if places[xx][yy - 1] == 'P':
res = 0
break
elif dy[i] == 1: # 우
if yy < 4:
if places[xx][yy + 1] == 'P':
res = 0
break
elif places[xx][yy] == 'P':
res = 0
break
if res == 0:
break
return res
def solution(places):
answer = []
for i in range(len(places)):
res = bfs(places[i], 0, 0)
answer.append(res)
return answer
해결한 풀이
굳이 상하좌우를 조건을 달아서 하나하나 체크할 필요가 없었다.
from collections import deque
def bfs(place, x, y):
res = 1
visited = [[0] * len(place) for _ in range(len(place))]
visited[x][y] = 1
dx = [-1, 1, 0, 0] # 상하좌우
dy = [0, 0, -1, 1]
queue = deque()
queue.append([x, y, 0])
while queue:
x, y, z = queue.popleft() # z는 거리
for i in range(4):
xx = x + dx[i]
yy = y + dy[i]
if 0 <= xx < 5 and 0 <= yy < 5 and not visited[xx][yy]:
if place[xx][yy] == 'O' and z < 1:
visited[xx][yy] = 1
queue.append([xx, yy, z + 1])
else:
if place[xx][yy] == 'P':
res = 0
break
if res == 0:
break
return res
def solution(places):
answer = []
for place in places:
status = 1
for i in range(5):
for j in range(5):
if place[i][j] == 'P':
status = bfs(place, i, j)
if status == 0:
break
if status == 0:
break
answer.append(status)
return answer