폴란드 왕자 구사과는 다음과 같은 수를 좋아한다.
- 0과 1로만 이루어져 있어야 한다.
- 1이 적어도 하나 있어야 한다.
- 수의 길이가 100 이하이다.
- 수가 0으로 시작하지 않는다.
각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다.
from collections import deque
t = int(input())
for _ in range(t):
n = int(input())
via = [-1] * n # 이전 수
how = [-1] * n # 0 붙였는지 / 1 붙였는지
dist = [-1] * n # 수의 길이
# 출발점
q = deque()
q.append(1 % n)
how[1%n] = 1
dist[1%n] = 0
while q:
now = q.popleft()
for i in [0,1]:
next = (now*10 + i) % n
if dist[next] == -1:
via[next] = now
how[next] = i
dist[next] = dist[now] + 1 # 1글자만 추가되니까
q.append(next)
if dist[0] == -1: # n의 배수가 없다면
print('BRAK')
else:
ans = ''
idx = 0
while idx != -1:
ans += str(how[idx])
idx = via[idx]
print(ans[::-1])만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다.
즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.
from collections import deque
dist = [[-1]*2 for _ in range(500000+1)]
# dist[i][0] : i 위치에 가장 빨리 도착 할 수 있는 짝수 시간
# dist[i][1] : i 위치에 가장 빨리 도착 할 수 있는 홀수 시간
n, k = map(int, input().split())
## 1. 언니
# 출발점
q = deque()
q.append((n, 0))
dist[n][0] = 0 # 0초 시작
while q:
x, t = q.popleft()
for y in [x+1, x-1, 2*x]:
if 0 <= y <= 500000: # (범위 체크)
if dist[y][1-t] == -1:
q.append((y, 1-t))
dist[y][1-t] = dist[x][t] + 1
## 2. 동생
ans = -1
t = 0
while True:
k += t # k : 동생의 위치 (동생도 매초 1씩 누적증가하면서 이동)
if k > 500000:
break
if dist[k][t % 2] <= t: # 언니가 동생보다 빨리 도착할 수 있으면 -> 정답 (x-1 / x+1 을 반복하면서 동생을 기다리면 되기 때문)
ans = t
break
t += 1
print(ans)크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다.
격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다.
직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자.
격자판의 각 칸에는 빈 칸 또는 벽이 있다. 직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자판을 벗어날 수 없다.
직사각형은 한 번에 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 한 칸 이동시킬 수 있다.
from collections import deque
dx = [-1,0,1,0]
dy = [0,1,0,-1]
# 입력
n, m = map(int, input().split())
a = [[0]*(m+1) for _ in range(n+1)]
s = [[0]*(m+1) for _ in range(n+1)] # 누적합 배열 (시간 효율성 높일)
d = [[-1]*(m+1) for _ in range(n+1)] # 방문 표시 배열
for i in range(1, n+1):
a[i][1:] = list(map(int, input().split()))
h, w, sx, sy, fx, fy = map(int, input().split())
# 누적합 배열 구하기
for i in range(1, n+1):
for j in range(1, m+1):
s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + (a[i][j]) # 0: 빈칸 / 1: 벽 임을 활용
# 값 구하는 함수
def get_sum(x1, y1, x2, y2):
return s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]
# BFS 탐색
q = deque()
q.append((sx, sy))
d[sx][sy] = 0 # 0초
while q:
x, y = q.popleft()
for k in range(4):
nx, ny = x+dx[k], y+dy[k]
if 1 <= nx and nx+h-1 < (n+1) and 1 <= ny and ny+w-1 < (m+1):
if get_sum(nx, ny, nx+h-1, ny+w-1) == 0: # 모든 직사각형 칸이 빈칸이면
if d[nx][ny] == -1:
q.append((nx, ny))
d[nx][ny] = d[x][y] + 1
print(d[fx][fy])입력으로 교실의 지도가 주어진다. 각각의 정사각형 블록은 다음과 같이 4가지 종류가 있다.
- S : 지금 민식이가 있는 곳이다. 이곳이 민식이가 배달을 시작하는 곳이다.
- C : 민식이가 반드시 선물을 배달해야 하는 곳이다. 이러한 블록은 정확하게 2개 있다.
- # : 민식이가 갈 수 없는 곳이다.
- . : 민식이가 자유롭게 지나갈 수 있는 곳이다.
민식이가 한 블록 동서남북으로 이동하는데는 1분이 걸린다. 민식이는 네가지 방향 중 하나로 이동할 수 있으며, 교실을 벗어날 수 없다.
민식이가 선물을 배달해야 하는 곳에 들어갈 때, 민식이는 그 곳에 있는 사람 모두에게 선물을 전달해야 한다.
이 상황은 동시에 일어나며, 추가적인 시간이 소요되지 않는다.
민식이는 어느 누구도 자신을 보지 않았으면 하기 때문에, 멈추지 않고 매 시간마다 방향을 바꿔야 한다.
이 말은 같은 방향으로 두 번 연속으로 이동할 수 없다는 말이다.
민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.
import sys
from collections import deque
dx = [-1,0,1,0]
dy = [0,1,0,-1]
# 입력
input = sys.stdin.readline
n, m = map(int, input().split())
a = [input().strip() for _ in range(n)]
d = [ [ [[-1]*4 for _ in range(4)] for _ in range(m) ] for _ in range(n) ] # D[위치 x][위치 y][방향 0~1][선물의 상태 0~1]
# s : 선물 받은 상태 (0: 0개 찾음 / 1: C1만 찾음 / 2: C2만 찾음 / 3: 2개 모두 찾음)
# 입력 배열로 부터 정보 구하기
ans = -1
x1, y1, x2, y2 = -1,-1,-1,-1
q = deque()
for i in range(n):
for j in range(m):
if a[i][j] == 'S':
for k in range(4):
q.append((i, j, k, 0))
d[i][j][k][0] = 0 # 0초에서 시작
elif a[i][j] == 'C':
if x1 == -1:
x1 = i
y1 = j
else:
x2 = i
y2 = j
# BFS 탐색
while q:
x, y, direction, s = q.popleft()
# 종료 시그널
if s == 3:
ans = d[x][y][direction][s]
break
for k in range(4):
if direction == k:
continue # 같은 방향은 연이어 갈 수 없음
nx, ny = x+dx[k], y+dy[k]
if 0<= nx <n and 0<= ny <m:
if a[nx][ny] != '#': # 갈 수 없는 칸만 아니면
ns = s
if a[nx][ny] == 'C':
if x1 == nx and y1 == ny:
ns |= 1
else:
ns |= 2
if d[nx][ny][k][ns] == -1:
q.append((nx, ny, k, ns))
d[nx][ny][k][ns] = d[x][y][direction][s] + 1
print(ans)크기가 N×N인 체스판이 있고, 체스판의 각 칸에는 1부터 N2까지의 정수가 한 번씩 적혀있다.
지학이는 이 체스판을 이용해서 재미있는 게임을 해보려고 한다.
지학이가 가지고 있는 말은 나이트, 비숍, 룩이다.
가장 먼저 1이 적혀있는 칸에 말 하나를 놓는다. 그 다음, 1, 2, ..., N2 순서로 이동시키려고 한다.
먼저, 1에 나이트, 비숍, 룩 중 하나를 놓는다. 그 다음, 말을 이동시켜서 2가 적힌 칸으로 이동시킨다. 1에서 2로 이동시킬 때, 다른 수가 적힌 칸을 방문할 수도 있다.
그 다음에는 3이 적힌 칸으로 이동시키고, ..., N2이 적힌 칸으로 이동시킨다. 같은 칸을 여러 번 방문하는 것도 가능하다.
지학이가 1초 동안 할 수 있는 행동은 체스판 위에 놓인 말을 이동시키거나, 다른 말로 바꾸는 것이다.
1에서 출발해서, 2, 3, ..., N2-1을 방문하고, N2까지 도착하는데 걸리는 시간의 최솟값을 구해보자.
from collections import deque
# 나이트
dx1 = [-2,-2, -1, 1, 2, 2, 1, -1]
dy1 = [-1, 1, 2, 2, 1, -1, -2, -2]
# 룩
dx2 = [-1,0,1,0]
dy2 = [0,1,0,-1]
# 비숍
dx3 = [-1,1,1,-1]
dy3 = [1,1,-1,-1]
# 입력
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
# D[r][c][현재 num][말 번호 piece]
d = [[[ [-1] * 3 for piece in range(n**2)] for j in range(n)] for i in range(n)]
q = deque()
for i in range(n):
for j in range(n):
a[i][j] -= 1 # 0~(N**2-1) 로 범위 조정하기 위함
if a[i][j] == 0:
for piece_idx in range(3):
q.append((i, j, 0, piece_idx))
d[i][j][0][piece_idx] = 0 # 0초에서 시작 (출발점 정의)
# BFS 탐색
ans = -1
while q:
x, y, num, piece = q.popleft()
# 종료 시그널
if num == n**2 -1:
if ans == -1 or ans > d[x][y][num][piece]:
ans = d[x][y][num][piece] ## MIN 값 업데이트
# 나머지 - 다음 단계 수행
## 액션 1) 말 바꾸기
for idx in range(3):
if idx == piece:
continue
if d[x][y][num][idx] == -1:
d[x][y][num][idx] = d[x][y][num][piece] + 1
q.append((x, y, num, idx))
## 액션 2) 말 이동시키기
if piece == 0: # 나이트
for k in range(8):
nx, ny = x+dx1[k], y+dy1[k]
if 0<=nx<n and 0<=ny<n:
next_num = num
if a[nx][ny] == (num + 1):
next_num = (num + 1) # (바로 다음 수 갈 수 있으면 이동해서 시간 효율화)
if d[nx][ny][next_num][piece] == -1:
d[nx][ny][next_num][piece] = d[x][y][num][piece] + 1
q.append((nx, ny, next_num, piece))
elif piece == 1: # 룩
for k in range(4):
l = 1
while True:
nx, ny = x+dx2[k]*l, y+dy2[k]*l
if 0<=nx<n and 0<=ny<n:
next_num = num
if a[nx][ny] == (num + 1):
next_num = (num + 1) # (바로 다음 수 갈 수 있으면 이동해서 시간 효율화)
if d[nx][ny][next_num][piece] == -1:
d[nx][ny][next_num][piece] = d[x][y][num][piece] + 1
q.append((nx, ny, next_num, piece))
else:
break
l += 1
else: # 비숍
for k in range(4):
l = 1
while True:
nx, ny = x+dx3[k]*l, y+dy3[k]*l
if 0<=nx<n and 0<=ny<n:
next_num = num
if a[nx][ny] == (num + 1):
next_num = (num + 1) # (바로 다음 수 갈 수 있으면 이동해서 시간 효율화)
if d[nx][ny][next_num][piece] == -1:
d[nx][ny][next_num][piece] = d[x][y][num][piece] + 1
q.append((nx, ny, next_num, piece))
else:
break
l += 1
print(ans)숨바꼭질 5 과 같은 문제
+ <가장 빠른 시간으로 찾는 방법이 몇 가지 인지> 도 같이 구하는 조건이 추가됨.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.
from collections import deque
MAX = 100000*2
check = [False] * MAX
dist = [0] * MAX
cnt = [0] * MAX
# 입력
n, k = map(int, input().split())
q = deque()
q.append(n)
check[n] = True
dist[n] = 0
cnt[n] = 1
# BFS 탐색
while q:
now = q.popleft()
for next in [now-1, now+1, 2*now]:
if 0<= next < MAX:
# (1) 아직 방문한 적 없을 때
if check[next] == False:
q.append(next)
check[next] = True
dist[next] = dist[now] + 1
cnt[next] = cnt[now]
# (2) 이미 방문한 적 있고, 현재 경우도 최단거리가 같을 때
elif dist[next] == (dist[now] + 1):
cnt[next] += cnt[now]
print(dist[k])
print(cnt[k])상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다.
빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다.
상근이는 상하좌우로만 이동할 수 있다.
상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.
from collections import deque
dx = [-1,0,1,0]
dy = [0,1,0,-1]
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
a = ['*.'+input()+'.*' for _ in range(n)]
# 테두리에 벽 한층 + 빈칸 한층 지도 넓히기
n += 4
m += 4
a = ['*'*m, '*'+'.'*(m-2)+'*'] + a + ['*'+'.'*(m-2)+'*', '*'*m]
key = set(input())
# BFS 탐색
ans = 0
check = [[False]*(m) for _ in range(n)]
door = [deque() for alpha in range(26)]
q = deque()
q.append((1, 1))
check[1][1] = True
while q:
x, y = q.popleft()
for k in range(4):
nx, ny = x+dx[k], y+dy[k]
# 불가능
if check[nx][ny] == True:
continue
if a[nx][ny] == '*':
continue
# 가능
check[nx][ny] = True
if a[nx][ny] == '$': # 문서
ans += 1
q.append((nx, ny))
elif a[nx][ny] == '.': # 빈칸
q.append((nx, ny))
elif 'A' <= a[nx][ny] <= 'Z': # 문 - 열거나 / 못 열거나
if a[nx][ny].lower() in key:
q.append((nx, ny))
else:
door[ord(a[nx][ny]) - ord('A')].append((nx, ny))
elif 'a' <= a[nx][ny] <= 'z': # 열쇠 - 줍기
q.append((nx, ny))
if not a[nx][ny] in key:
key.add(a[nx][ny])
q.extend(door[ord(a[nx][ny]) - ord('a')])
print(ans)1
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz
3
{'a', 'c', 'p', 'x', 'z'}
구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다.
각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다. 한 칸 위에 성이 두 개 이상인 경우는 없다.
게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다.
제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 이런 식으로 라운드가 진행된다.
각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸으로 확장한다.
플레이어 i는 자신의 성이 있는 곳에서 Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다.
위, 왼쪽, 오른쪽, 아래로 인접한 칸으로만 이동할 수 있으며, 벽이나 다른 플레이어의 성이 있는 곳으로는 이동할 수 없다.
성을 다 건설한 이후엔 다음 플레이어가 턴을 갖는다.
모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다. 게임판의 초기 상태가 주어졌을 때, 최종 상태를 구해보자.
from collections import deque
dx = [-1,0,1,0]
dy = [0,1,0,-1]
n, m, p = map(int, input().split())
s = [0] + list(map(int, input().split()))
a = [[0]*m for _ in range(n)]
for i in range(n):
line = input()
for j in range(m):
if line[j] == '.':
a[i][j] = 0 # 빈칸
elif line[j] == '#':
a[i][j] = -1 # 벽
else:
a[i][j] = ord(line[j]) - ord('0') # 플레이어 번호
q = [deque() for _ in range(p+1)] # 현재 턴의 시작점을 담을 큐
next_q = [deque() for _ in range(p+1)] # 다음 턴의 시작점을 담을 큐
for i in range(n):
for j in range(m):
if a[i][j] > 0:
q[a[i][j]].append((i, j))
# 게임 시뮬레이션
while True:
ok = False
for who in range(1, p+1):
d = [[0]*m for _ in range(n)]
while q[who]:
ok = True
x, y = q[who].popleft()
if d[x][y] == s[who]: # 해당 턴 해당 플레이어의 확장 끝점 -> 다음 턴 방문 큐에 넣기
next_q[who].append((x, y))
if a[x][y] > 0 and a[x][y] != who: # 이미 다른 번호의 플레이어가 놓았던 곳이라면 pass
continue
a[x][y] = who
for k in range(4):
nx, ny = x+dx[k], y+dy[k]
if 0<= nx < n and 0<= ny < m:
if a[nx][ny] == 0: # 빈칸 && 아직 놓은 적 없는 곳
d[nx][ny] = d[x][y]+1
if d[nx][ny] <= s[who]:
a[nx][ny] = who
q[who].append((nx, ny))
q[who] = next_q[who]
next_q[who] = deque()
if ok == False:
break
# 답 출력
ans = [0] * (p+1)
for i in range(n):
for j in range(m):
if a[i][j] > 0:
ans[a[i][j]] += 1
print(' '.join(map(str, ans[1:])))print(' '.join(map(str, ans[1:])))- 구슬 탈출 2와 같은 문제 -> 최대 10번 횟수 제한 O -> <브루트포스> 가능
- 구슬 탈출 4 -> 횟수 제한 X -> <BFS> 로 풀어야 함
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 어떻게 움직여도 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
from collections import deque
import copy
dx = [-1,0,1,0]
dy = [0,1,0,-1]
# 입력
n, m = map(int, input().split())
a = [list(input()) for _ in range(n)]
for i in range(n):
for j in range(m):
if a[i][j] == 'O': # 구멍
hx, hy = i, j
elif a[i][j] == 'R': # 빨간구슬 초기 위치
rx, ry = i, j
a[i][j] = '.'
elif a[i][j] == 'B': # 빨간구슬 초기 위치
bx, by = i, j
a[i][j] = '.'
def simulate(a, k, x, y):
if a[x][y] == '.':
return (False, False, x, y)
n = len(a)
m = len(a[0])
moved = False
while True:
nx, ny = x+dx[k], y+dy[k]
if a[nx][ny] == '#':
return (moved, False, x, y)
elif a[nx][ny] in 'RB':
return (moved, False, x, y)
elif a[nx][ny] == '.':
moved = True
a[x][y], a[nx][ny] = a[nx][ny], a[x][y]
x, y = nx, ny
elif a[nx][ny] == 'O':
a[x][y] = '.'
moved = True
return (moved, True, x, y)
def go(b, rx, ry, bx, by, direction):
a = copy.deepcopy(b)
a[rx][ry] = 'R'
a[bx][by] = 'B'
hole1 = False
hole2 = False
while True:
rmoved, rhole, rx, ry = simulate(a, direction, rx, ry)
bmoved, bhole, bx, by = simulate(a, direction, bx, by)
if not rmoved and not bmoved:
break # 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
if rhole:
hole1 = True
if bhole:
hole2 = True
return (hole1, hole2, rx, ry, bx, by)
# BFS 탐색
d = [[[[-1]*m for bx in range(n)] for ry in range(m)] for rx in range(n)] # D[빨간구슬 rx][빨간구슬 ry][파란구슬 bx][파란구슬 by]
q = deque()
q.append((rx, ry, bx, by))
d[rx][ry][bx][by] = 0
ans = -1
found = False
while q:
rx, ry, bx, by = q.popleft()
for k in range(4):
hole1, hole2, nrx, nry, nbx, nby = go(a, rx, ry, bx, by, k)
if hole2 == True: # 파란 구슬이 구멍을 통과하면 실패
continue
if hole1 == True: # 빨간 구슬만 구멍을 통과하면 성공 (게임 종료)
ans = d[rx][ry][bx][by] + 1
found = True
break
if d[nrx][nry][nbx][nby] == -1:
q.append((nrx,nry,nbx,nby))
d[nrx][nry][nbx][nby] = d[rx][ry][bx][by] + 1
if found == True:
break
print(ans)5 5
#####
#..B#
#.#.#
#RO.#
#####
1
지도는 총 2개의 줄로 나누어져 있으며, 각 줄은 N개의 칸으로 나누어져 있다.
칸은 위험한 칸과 안전한 칸으로 나누어져 있고, 안전한 칸은 유저가 이동할 수 있는 칸, 위험한 칸은 이동할 수 없는 칸이다.
가장 처음에 유저는 왼쪽 줄의 1번 칸 위에 서 있으며, 매 초마다 아래 세 가지 행동중 하나를 해야 한다.
- i+1번 칸으로 이동한다.
- i-1번 칸으로 이동한다.
- 반대편 줄로 점프한다. 이때, 원래 있던 칸보다 k칸 앞의 칸으로 이동해야 한다. i+k번 칸으로 이동해야 한다.
N번 칸보다 더 큰 칸으로 이동하는 경우에는 게임을 클리어한 것이다.
게임을 재밌게 하기 위해서, 게임을 시작한지 1초가 지나면 1번 칸이 사라지고, 2초가 지나면 2번 칸이 사라진다.
편의상 유저가 먼저 움직이고, 칸이 사라진다고 가정한다.
각 칸의 정보가 주어졌을 때, 게임을 클리어 할 수 있는지, 없는지 구하는 프로그램을 작성하시오.
게임을 클리어할 수 있으면 1을, 없으면 0을 출력한다.
from collections import deque
n, k = map(int, input().split())
a = [list(input()) for _ in range(2)]
dirs = [(0, 1), (0, -1), (1, k)]
dist = [[-1]*n for _ in range(2)]
q = deque()
q.append((0, 0))
dist[0][0] = 0
ok = False
# 게임 시뮬레이션
while q:
x, kk = q.popleft()
for dx, dk in dirs:
nx, nkk = (x+dx)%2, kk+dk
# 게임 종료 시그널
if nkk >= n:
ok = True
break
# 불가능한 경우들
if nkk < 0:
continue
if dist[nx][nkk] != -1:
continue
if nkk < dist[x][kk]+1: # 1초에 한 칸씩 각 줄의 첫 칸이 사라지는 기능 때문
continue
if a[nx][nkk] == '0': # 위험한 칸
continue
# 가능한 경우 - 나머지 다음 수행
q.append((nx, nkk))
dist[nx][nkk] = dist[x][kk] + 1
if ok == True:
break
print(1 if ok==True else 0)