https://school.programmers.co.kr/learn/courses/30/lessons/60063
1) 내 첫 코드
from collections import deque
def isInside(x, y, N):
if 0<=x and x<N and 0<=y and y<N:
return True
else:
return False
def solution(board):
answer = 0
N = len(board)
visited = set()
q = deque()
q.append([0, 0, 0, 1, 0, 0])
visited.add("0001")
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
dx2 = [1, -1]
dy2 = [0, 0]
dx3 = [0, 0]
dy3 = [1, -1]
answer = 0
while q:
x1, y1, x2, y2, direction, time = q.popleft()
print(x1, y1, x2, y2, direction, time)
if x1 == x2 and y1 > y2:
y1, y2 = y2, y1
if y1 == y2 and x1 > x2:
x1, x2 = x2, x1
if (x1 == N-1 and y1 == N-1) or (x2 == N-1 and y2 == N-1):
answer = time
break
for i in range(4):
nx1 = x1 + dx[i]
ny1 = y1 + dy[i]
nx2 = x2 + dx[i]
ny2 = y2 + dy[i]
tmp1 = ""
if nx1 == nx2 and ny1 > ny2:
tmp1 = str(nx1) + str(ny2) + str(nx2) + str(ny1)
elif ny1 == ny2 and nx1 > nx2:
tmp1 = str(nx2) + str(ny1) + str(nx1) + str(ny2)
else:
tmp1 = str(nx1) + str(ny1) + str(nx2) + str(ny2)
if isInside(nx1, ny1, N) and isInside(nx2, ny2, N) and board[nx1][ny1] == 0 and board[nx2][ny2] == 0 and tmp1 not in visited:
q.append([nx1 ,ny1, nx2, ny2, direction, time+1])
visited.add(tmp1)
## 가로일 때
if direction == 0:
for i in range(2):
nx1 = x1
ny1 = y1
nx2 = x1 + dx2[i]
ny2 = y1 + dy2[i]
tmp1 = ""
if nx1 == nx2 and ny1 > ny2:
tmp1 = str(nx1) + str(ny2) + str(nx2) + str(ny1)
elif ny1 == ny2 and nx1 > nx2:
tmp1 = str(nx2) + str(ny1) + str(nx1) + str(ny2)
else:
tmp1 = str(nx1) + str(ny1) + str(nx2) + str(ny2)
if isInside(nx1, ny1, N) and isInside(nx2, ny2, N) and board[nx1][ny1] == 0 and board[nx2][ny2] == 0 and tmp1 not in visited:
if i == 0 and board[x1+1][y1+1] == 0:
q.append([nx1, ny1, nx2, ny2, 1, time + 1])
visited.add(tmp1)
elif i == 1 and board[x1-1][y1+1] == 0:
q.append([nx1, ny1, nx2, ny2, 1, time + 1])
visited.add(tmp1)
for i in range(2):
nx1 = x2 + dx2[i]
ny1 = y2 + dy2[i]
nx2 = x2
ny2 = y2
tmp1 = ""
if nx1 == nx2 and ny1 > ny2:
tmp1 = str(nx1) + str(ny2) + str(nx2) + str(ny1)
elif ny1 == ny2 and nx1 > nx2:
tmp1 = str(nx2) + str(ny1) + str(nx1) + str(ny2)
else:
tmp1 = str(nx1) + str(ny1) + str(nx2) + str(ny2)
if isInside(nx1, ny1, N) and isInside(nx2, ny2, N) and board[nx1][ny1] == 0 and board[nx2][
ny2] == 0 and tmp1 not in visited:
if i == 0 and board[x2 + 1][y2 - 1] == 0:
q.append([nx1, ny1, nx2, ny2, 1, time + 1])
visited.add(tmp1)
elif i == 1 and board[x2 - 1][y2 - 1] == 0:
q.append([nx1, ny1, nx2, ny2, 1, time + 1])
visited.add(tmp1)
else:
for i in range(2):
nx1 = x1
ny1 = y1
nx2 = x1 + dx3[i]
ny2 = y1 + dy3[i]
tmp1 = ""
if nx1 == nx2 and ny1 > ny2:
tmp1 = str(nx1) + str(ny2) + str(nx2) + str(ny1)
elif ny1 == ny2 and nx1 > nx2:
tmp1 = str(nx2) + str(ny1) + str(nx1) + str(ny2)
else:
tmp1 = str(nx1) + str(ny1) + str(nx2) + str(ny2)
if isInside(nx1, ny1, N) and isInside(nx2, ny2, N) and board[nx1][ny1] == 0 and board[nx2][ny2] == 0 and tmp1 not in visited:
if i == 0 and board[x1+1][y1+1] == 0:
q.append([nx1, ny1, nx2, ny2, 0, time + 1])
visited.add(tmp1)
elif i == 1 and board[x1+1][y1-1] == 0:
q.append([nx1, ny1, nx2, ny2, 0, time + 1])
visited.add(tmp1)
for i in range(2):
nx1 = x2 + dx3[i]
ny1 = y2 + dy3[i]
nx2 = x2
ny2 = y2
tmp1 = ""
if nx1 == nx2 and ny1 > ny2:
tmp1 = str(nx1) + str(ny2) + str(nx2) + str(ny1)
elif ny1 == ny2 and nx1 > nx2:
tmp1 = str(nx2) + str(ny1) + str(nx1) + str(ny2)
else:
tmp1 = str(nx1) + str(ny1) + str(nx2) + str(ny2)
if isInside(nx1, ny1, N) and isInside(nx2, ny2, N) and board[nx1][ny1] == 0 and board[nx2][
ny2] == 0 and tmp1 not in visited:
if i == 0 and board[x2 - 1][y2 + 1] == 0:
q.append([nx1, ny1, nx2, ny2, 0, time + 1])
visited.add(tmp1)
elif i == 1 and board[x2 - 1][y2 - 1] == 0:
q.append([nx1, ny1, nx2, ny2, 0, time + 1])
visited.add(tmp1)
return answer
2) 참고 코드
from collections import deque
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
MAX = float('inf')
def solution(board):
N = len(board)
answer = 0
visited = set()
q = deque([(0,0,0,0)])
while q :
x, y, r, t = q.popleft()
if (x, y) == (N-1, N-1) or (x + dx[r], y + dy[r]) == (N-1, N-1) :
answer = t
break
if (x, y, r) in visited or (x + dx[r], y + dy[r], (r+2) % 4) in visited :
continue
visited.add((x, y, r))
for i in range(4) :
ax, ay = x + dx[i], y + dy[i]
if not -1 < ax < N or not -1 < ay < N or board[ay][ax] == 1:
continue
_ax, _ay = ax + dx[r], ay + dy[r]
if not -1 < _ax < N or not -1 < _ay < N or board[_ay][_ax] == 1:
continue
q.append((ax, ay, r, t+1))
for i in [-1, 1] :
_r = (r + i) % 4
ax, ay = x + dx[_r], y + dy[_r]
if not -1 < ax < N or not -1 < ay < N or board[ay][ax] == 1:
continue
cx, cy = ax + dx[r], ay + dy[r]
if board[cy][cx] == 1 :
continue
q.append((x, y, _r, t+1))
x, y, r = x + dx[r], y + dy[r], (r+2) % 4
for i in [-1, 1] :
_r = (r + i) % 4
ax, ay = x + dx[_r], y + dy[_r]
if not -1 < ax < N or not -1 < ay < N or board[ay][ax] == 1:
continue
cx, cy = ax + dx[r], ay + dy[r]
if board[cy][cx] == 1 :
continue
q.append((x, y, _r, t+1))
return answer2) 해설
- 나는 4개의 좌표를 이용해서 문제를 풀었는데,
2개의 좌표+방향으로도 문제를 풀 수 있다
-> 어떻게 풀었는지 잘 보고 습득하도록 하자.
hello