문제설명
해결 방법
먼저 BFS응용 문제이고 내 해결방법은 이렇다
1. 회전은 8가지경우가(세로or가로, 축2가지, 회전방향) 있고 이동은(상, 하,좌,우)4가지가 있다
2. 한지점에서 12가지 경우로 이동후 이를 큐에다가 집어넣어서 순차적으로 마지막지점에 왔을 때 그 값이 최소시간이 되므로 리턴 하려 했지만
무조건 12가지가 아니었고
매우 복잡하게 짜다보니 200라인이 넘어갔다.
해답 코드
일단은 구현해본 코드이다.
def out(size, y1, x1):
#한지점이 맵밖에 나가면 True 리턴 아니라면 False 리턴
if y1 >= 0 and y1 < size and x1 >= 0 and x1 < size:
return False
else:
return True
def spin(board, S1, S2, ud):
#위함수는 S1을 회전축으로 하고 S2를 움직임
N = len(board)
#먼저 로봇의 형태가 가로인지 세로인지 확인
if S1[0] == S2[0]:
#가로일 때
if ud == 1:
#위로 회전할 때
if S1[1] < S2[1]:
#회전축이 왼쪽에 있을 때
if out(N, S2[0]-1, S2[1]) == False and out(N, S2[0]-1, S2[1]-1) == False:
#이동반경이 맵안에 있어야하고
if board[S2[0]-1][S2[1]] == 0 and board[S2[0]-1][S2[1]-1] == 0:
#이동방경이 벽이 아니라면 회전 가능
S2[0] -= 1
S2[1] -= 1
S1[2] += 1
S2[2] += 1
return S1, S2
else:
#회전축이 오른쪽에 있을 때
if out(N, S1[0]-1, S1[1]) == False and out(N, S1[0]-1, S1[1]-1) == False:
#이동반경이 맵안에 있어야하고
if board[S1[0]-1][S1[1]] == 0 and board[S1[0]-1][S1[1]-1] == 0:
#이동방경이 벽이 아니라면 회전 가능
S2[0] -= 1
S2[1] += 1
S1[2] += 1
S2[2] += 1
return S1, S2
else:
#아래로 회전할 때
if S1[1] < S2[1]:
#회전축이 왼쪽에 있을 때
if out(N, S1[0]+1, S1[1]) == False and out(N, S1[0]+1, S1[1]+1) == False:
#이동반경이 맵안에 있어야하고
if board[S1[0]+1][S1[1]] == 0 and board[S1[0]+1][S1[1]+1] == 0:
#이동방경이 벽이 아니라면 회전 가능
S2[0] +=1
S2[1] -=1
S1[2] +=1
S2[2] +=1
return S1, S2
else:
#회전축이 오른쪽에 있을 때
if out(N, S2[0]+1, S2[1]) == False and out(N, S2[0]+1, S2[1]+1) == False:
#이동반경이 맵안에 있어야하고
if board[S2[0]+1][S2[1]] == 0 and board[S2[0]+1][S2[1]+1] == 0:
#이동방경이 벽이 아니라면 회전 가능
S2[0] +=1
S2[1] +=1
S1[2] +=1
S2[2] +=1
return S1, S2
else:
#세로일 때
if ud == 1:
#오른쪽으로 회전할 때
if S1[0] < S2[0]:
#회전축이 위에있을 때
if out(N, S2[0], S2[1]+1) == False and out(N, S2[0]-1, S2[1]+1) == False:
#이동반경이 맵안에 있어야하고
if board[S2[0]][S2[1]+1] == 0 and board[S2[0]-1][S2[1]+1] == 0:
#이동방경이 벽이 아니라면 회전 가능
S2[0] -=1
S2[1] +=1
S1[2] +=1
S2[2] +=1
return S1, S2
else:
#회전축이 아래에 있을 때
if out(N, S1[0], S1[1]+1) == False and out(N, S1[0]-1, S1[1]+1) == False:
#이동반경이 맵안에 있어야하고
if board[S1[0]][S1[1]+1] == 0 and board[S1[0]-1][S1[1]+1] == 0:
#이동방경이 벽이 아니라면 회전 가능
S2[0] +=1
S2[1] +=1
S1[2] +=1
S2[2] +=1
return S1, S2
else:
#왼쪽으로 회전할 때
if S1[0] < S2[0]:
#회전축이 위에있을 때
if out(N, S2[0], S2[1]-1) == False and out(N, S2[0]-1, S2[1]-1) == False:
#이동반경이 맵안에 있어야하고
if board[S2[0]][S2[1]-1] == 0 and board[S2[0]-1][S2[1]-1] == 0:
#이동방경이 벽이 아니라면 회전 가능
S2[0] -=1
S2[1] -=1
S1[2] +=1
S2[2] +=1
return S1, S2
else:
#회전축이 아래에 있을 때
if out(N, S1[0], S1[1]-1) == False and out(N, S1[0]-1, S1[1]-1) == False:
#이동반경이 맵안에 있어야하고
if board[S1[0]][S1[1]-1] == 0 and board[S1[0]-1][S1[1]-1] == 0:
#이동방경이 벽이 아니라면 회전 가능
S2[0] +=1
S2[1] -=1
S1[2] +=1
S2[2] +=1
return S1, S2
return S1, S2
from collections import deque
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
def solution(board):
INF = 2100000000
answer = 0
#맵의 크기 N
N = len(board)
#각지점의 도달 최소시간 저장 리스트 visit
visit = [[INF] * N for _ in range(N)]
#큐에다가 시작지점 넣어주기 visit처리
Q = deque()
Q.append([0,0,0])
Q.append([0,1,0])
visit[0][0] = 0
visit[0][1] = 0
#BFS 탐색!!!
count = 0
while Q:
if visit[N-1][N-1] != INF:
break
s1 = Q.popleft()
s2 = Q.popleft()
# for i in range(N):
# for j in range(N):
# if visit[i][j] == INF:
# print('-1', end = '|')
# else:
# print(visit[i][j], end = '|')
# print()
# print('----------------')
#4가지 이동경우와 8번의 회전 경우의수 탐색
for i in range(12):
if i < 4:
#이동만 할 때
new_s1 = list(s1)
new_s1[0] += dy[i]
new_s1[1] += dx[i]
new_s2 = list(s2)
new_s2[0] += dx[i]
new_s2[1] += dx[i]
#새로운 지점이 맵안에 있을 때
if out(N, new_s1[0], new_s1[1]) == False and out(N, new_s2[0], new_s2[1]) == False:
#새로운지점이 벽이 아닐 때
if board[new_s1[0]][new_s1[1]] == 0 and board[new_s2[0]][new_s2[1]] == 0:
#새로운 지점을 방문 하지 않았다면
if visit[new_s1[0]][new_s1[1]] == INF or visit[new_s2[0]][new_s2[1]] == INF:
visit[new_s1[0]][new_s1[1]] = min(visit[new_s1[0]][new_s1[1]], new_s1[2]+ 1)
visit[new_s2[0]][new_s2[1]] = min(visit[new_s2[0]][new_s2[1]], new_s2[2] + 1)
Q.append(new_s1)
Q.append(new_s2)
else:
#회전 했을 때
if i < 8:
#ud가 1일때
ud = 1
if i % 2 == 1:
#회전측이 s1일 때
new_s1, new_s2 = spin(board, s1, s2, ud)
#새로운 지점이 맵안에 있을 때
if out(N, new_s1[0], new_s1[1]) == False and out(N, new_s2[0], new_s2[1]) == False:
#새로운 지점을 방문 하지 않았다면
if visit[new_s1[0]][new_s1[1]] == INF or visit[new_s2[0]][new_s2[1]] == INF:
visit[new_s1[0]][new_s1[1]] = min(visit[new_s1[0]][new_s1[1]], new_s1[2]+ 1 + 1)
visit[new_s2[0]][new_s2[1]] = min(visit[new_s2[0]][new_s2[1]], new_s2[2]+ 1 + 1)
Q.append(new_s1)
Q.append(new_s2)
else:
#회전축이 s2일 때
new_s1, new_s2 = spin(board, s2, s1, ud)
#새로운 지점이 맵안에 있을 때
if out(N, new_s1[0], new_s1[1]) == False and out(N, new_s2[0], new_s2[1]) == False:
#새로운 지점을 방문 하지 않았다면
if visit[new_s1[0]][new_s1[1]] == INF or visit[new_s2[0]][new_s2[1]] == INF:
visit[new_s1[0]][new_s1[1]] = min(visit[new_s1[0]][new_s1[1]], new_s1[2] + 1)
visit[new_s2[0]][new_s2[1]] = min(visit[new_s2[0]][new_s2[1]], new_s2[2]+ 1)
Q.append(new_s1)
Q.append(new_s2)
else:
#ud가 -1일때
ud = -1
if i % 2 == 1:
#회전측이 s1일 때
new_s1, new_s2 = spin(board, s1, s2, ud)
#새로운 지점이 맵안에 있을 때
if out(N, new_s1[0], new_s1[1]) == False and out(N, new_s2[0], new_s2[1]) == False:
#새로운 지점을 방문 하지 않았다면
if visit[new_s1[0]][new_s1[1]] == INF or visit[new_s2[0]][new_s2[1]] == INF:
visit[new_s1[0]][new_s1[1]] = min(visit[new_s1[0]][new_s1[1]], new_s1[2]+ 1)
visit[new_s2[0]][new_s2[1]] = min(visit[new_s2[0]][new_s2[1]], new_s2[2]+ 1)
Q.append(new_s1)
Q.append(new_s2)
else:
#회전축이 s2일 때
new_s1, new_s2 = spin(board, s2, s1, ud)
#새로운 지점이 맵안에 있을 때
if out(N, new_s1[0], new_s1[1]) == False and out(N, new_s2[0], new_s2[1]) == False:
#새로운 지점을 방문 하지 않았다면
if visit[new_s1[0]][new_s1[1]] == INF or visit[new_s2[0]][new_s2[1]] == INF:
visit[new_s1[0]][new_s1[1]] = min(visit[new_s1[0]][new_s1[1]], new_s1[2]+ 1)
visit[new_s2[0]][new_s2[1]] = min(visit[new_s2[0]][new_s2[1]], new_s2[2]+ 1)
Q.append(new_s1)
Q.append(new_s2)
answer = visit[N-1][N-1]
return answer
board = [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]]
print(solution(board))단단히 잘못된!!! 코드다
제대로된 해결 방법
사실 내가 계속해서 틀린 핵심이유는 한가지 였다
움직이는 유닛이 한칸을 차지 하지않는데 visit리스트를
한칸을 차지하는 유닛일때나 쓸수있는 리스트였다.
너비우선 탐색의 본질을 더 봐야했었다.
그래서!!!
visit을 두지점이 담긴 set으로 하니 생각보다 어렵지 않게 할 수있었다.
제대로된 해답 코드
from collections import deque
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
def next_pos(matrix, p1, p2):
res = deque()
# 상하좌우 이동
for i in range(4):
if matrix[p1[0]+dy[i]][p1[1]+dx[i]] == 0 and matrix[p2[0]+dy[i]][p2[1]+dx[i]] == 0:
res.append(((p1[0]+dy[i], p1[1]+dx[i]),(p2[0]+dy[i], p2[1]+dx[i])))
# 회전 이동
if p1[0] == p2[0]:
#가로일 때
for d in [-1, 1]:
if matrix[p1[0]+d][p1[1]] == 0 and matrix[p2[0]+d][p2[1]] == 0:
res.append((p1, (p2[0]+d, p1[1])))
res.append(((p1[0]+d,p2[1]), p2))
else:
#세로일 때
for d in [-1, 1]:
if matrix[p1[0]][p1[1]+d] == 0 and matrix[p2[0]][p2[1]+d] == 0:
res.append((p1, (p1[0], p2[1]+d)))
res.append(((p2[0], p1[1]+d),p2))
return res
def solution(board):
answer = 0
N = len(board)
#외벽 만들어 주기
matrix = [[1] * (N+2) for _ in range(N+2)]
for i in range(N):
for j in range(N):
matrix[i][j] = board[i][j]
Q = deque()
Q.append([0, (0,0), (0,1)])
visit = set([((0,0), (0,1))])
#BFS탐색 시작
while Q:
cost, p1 , p2 = Q.popleft()
for new_p in next_pos(matrix, p1, p2):
#목적지일 때
if (new_p[0][0] == N-1 and new_p[0][1] == N-1) or (new_p[1][0] == N-1 and new_p[1][1] == N-1):
return cost+1
if new_p not in visit:
Q.append([cost+1, new_p[0], new_p[1]])
visit.add(new_p)
return answer다른사람들의 코드를 보고난후...
먼저 크게는 2가지가 신선했다.
-
map에다가 comfilm이라 해서 벽을 둘러쌌다.
이 방식으로 구현하니 out함수가 필요없고
탐색을 할 때마다 맵밖으로 나가는지 확인이 필요가 없었다. -
get_nextPos()함수!!
나는 이동할때 회전할때를 for문안에서 i의 크기에따라 나눌려고하니
코드가 길어지고 복잡해졌지만
위 함수를 이용하면 메인문이 좀더 단순해져서 훨씬단순한 코드였다!!!
삶의 질을 높여주는 개발자