Coding 공부

N = int(input())
def makePrimeNumber(num,idx):
    if idx == N:
        result.append(num)
    else:
        for last_num in range(1,10,2):
            new_num = num*10 + last_num
            if isPrime(new_num):
                makePrimeNumber(new_num,idx+1)
 
def isPrime(num):
    if num in prime_numbers:
        return True
    for i in range(2,int(num**0.5)+1):
        if num%i == 0:
            return False
    prime_numbers.add(num)
    return True
 
 
prime_numbers = set([2,3,5,7])
result = []
 
 
for num in [2,3,5,7]:
    makePrimeNumber(num,1)
result.sort()
 
for row in result:
    print(row)

이 문제는 처음에 모든 N자리의 숫자를 primnumber 인지를 구했더니 메모리초과가 났던 문제이다.

이 문제를 푸는 방법은 다음과 같다.

이 문제를 보면 우리는 제일 왼쪽부터 한자리숫자씩 늘리면서 모든 경우에 소수인 것을 구하는 것이다.

그러면 우리가 한자리숫자에서 소수인 것은 2,3,5,7 임을 알 수 있다.

그러면 제일 왼쪽은 무조건 2,3,5,7로 시작되게 해준다.

그리고 N자리를 dfs로 구해주면 된다.

현재 num에 10을 곱하고 끝자리를 바꿔가면서 그 값이 소수인지 판별해주면 된다.

그리고 우리는 한자리숫자를 제외한 두자리숫자부터는 끝 숫자부분이 홀수여야지만 소수가 될 가능성임을 알 수 있다.

그러므로 끝자리는 홀수들만 들어가게 해준다.

소수를 판별하는 방법은 이 수의 제곱근까지의 숫자까지 나눠가면서 나눠지는 경우가 있는지 확인해주면 된다.

그리고 한번 소수로 판별된 경우에는 두번 탐색할 수고를 덜기 위해, set에 저장해준다.

위와 같은 방식으로 N자리 숫자를 만들고

정렬 한뒤에 출력하면 된다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
 
N,M = map(int,input().split())
 
 
graph = [[] for _ in range(N+1)]
 
 
 
for ind in range(M):
    arr = list(map(int,input().split()))
    lens = len(arr)
 
    for arr_ind in range(lens-1):
        cur_node = arr[arr_ind]
        if arr_ind == 0:
            graph[cur_node].append([-1,arr[arr_ind+1],ind])
        else:
            graph[cur_node].append([arr[arr_ind-1],arr[arr_ind+1],ind])
 
start_node, end_node = map(int,input().split())
INF = float('inf')
distance_list = [INF for _ in range(N+1)]
visited_node = [True for _ in range(N+1)]
distance_list[start_node] = 0
queue = deque()
 
queue.append((start_node,0,-1))
 
while queue:
    node,cnt,prev_ind = queue.popleft()
    for left_node,right_node,position in graph[node]:
        if left_node != -1:
            if prev_ind == -1:
                distance_list[left_node] = cnt
                queue.append((left_node,cnt,position))
            else:
                temp = 1 if prev_ind != position else 0
                if distance_list[left_node] > cnt + temp:
                    distance_list[left_node] = cnt + temp
                    queue.append((left_node,cnt+temp,position))
        if right_node != -1:
            if prev_ind == -1:
                distance_list[right_node] = cnt
                queue.append((right_node,cnt,position))
            else:
                temp = 1 if prev_ind != position else 0
                if distance_list[right_node] > cnt + temp:
                    distance_list[right_node] = cnt + temp
                    queue.append((right_node,cnt+temp,position))
 
 
 
 
if distance_list[end_node] == INF:
    print(-1)
else:
    print(distance_list[end_node])

처음 풀었던 풀이는 좋은 풀이는 아닌것처럼 보인다.

처음 풀었던 방식은 다음과 같다. 현재 노드에 좌우 노드와 현재 노선을 집어넣어준다.

그리고 bfs를 하면서 노선이 바뀔때 그 값이 현재 있는 값보다 적으면 바꿔서 queue에 넣어주는 방식대로 했다.

이 방식의 문제점은 한 노선이 엄청 길면 모든 노선들을 전부 하나하나씩 다 탐색을 하는 것이다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
N,M = map(int,input().split())
 
graph = []
 
subway_routelist = [[] for _ in range(N+1)]
 
 
for route_ind in range(M):
    arr = set(map(int,input().split()))
    arr.remove(-1)
    for subway_num in arr:
        subway_routelist[subway_num].append(route_ind)
 
    graph.append(list(arr))
 
start_node, end_node = map(int,input().split())
visited = [-1 for _ in range(N+1)]
visited_subway = [-1 for _ in range(M)]
end_subway = []
 
for route_ind in range(M):
    if end_node in graph[route_ind]:
        end_subway.append(route_ind)
 
 
queue = deque()
route_cnt = 0
visited[end_node] = 0
for end_route in end_subway:
    visited_subway[end_route] = route_cnt
    for subway_num in graph[end_route]:
        if visited[subway_num] == -1:
            visited[subway_num] = route_cnt
            queue.append(subway_num)
 
if visited[start_node] != -1:
    print(0)
else:
        
    while queue:
        N = len(queue)
        for _ in range(N):
            node = queue.popleft()
            for route in subway_routelist[node]:
                if visited_subway[route] == -1:
                    visited_subway[route] = route_cnt + 1
                    for subway_num in graph[route]:
                        if visited[subway_num] == -1:
                            visited[subway_num] = route_cnt + 1
                            queue.append(subway_num)
        route_cnt += 1
        if visited[start_node] != -1:
            break
 
 
    print(visited[start_node])

이 풀이는 노선을 기준으로 bfs를 하는 방식이다.

먼저 사전 작업으로, subway_route_list에 현재 노선번호를 넣어준다.

graph에는 각 노선의 역정보를 넣어준다.

먼저 우리는 도착지점이 있는 route(노선)들을 전부 구한다. 그 노선이 있는 목록을 end_subway라고 하겠다.

그러면 우리는 이 route들의 모든 노선들은 환승이 없이 도착지점에 도착하는 것을 알 수 있다.

그러므로 우리는 visited_subway라는 노선의 방문을 체크하는 곳에 방문의 여부를 체크를 해준다.

그리고 난뒤에 우리는 이 노선(route)에 있는 역들도 전부 환승없이 방문 할 수 있는 것을 알 수 있다.

그러므로 역의 방문을 나타내는 visited에 방문을 체크해주고, 그때의 역번호를 queue에 넣어준다.

위와 같은 일련의 작업을 한뒤에는 우리가 구할 수 있는 것은 도착지점에서 한번의 환승도 없이 다닐 수 있는

모든 역들을 체크해준것이다.

그러면 우리는 현재 상태에서 start_node가 방문이 표시되었다 하면, 환승없이 start_node에서 end_node까지 갈수 있음을 알 수 있고,

그때는 0을 출력해준다.

만약 그렇지 않을때에는 bfs를 해주면 된다.

이 bfs는 하나의 queue 단위로 bfs를 돌려주면 되므로,

최초의 queue의 크기인 N만큼 popleft를 해주면서, 해당 역에서 갈 수 있는 노선을 갱신해주고,

이 노선에서 갈 수 있는 역 중에 가보지 않은 역들을 queue에 추가해주면된다.

이러한 방식을 통해 최소 환승 횟수를 알 수 있게 된다.

이 문제에서 주요한 점은 역을 중점으로 bfs를 돌리는 것이 아닌 노선을 중심으로 해서 bfs를 돌린다는 점을 주의해주면 된다.

import sys
import heapq
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
N,M = map(int,input().split())
 
 
 
INF = float('inf')
step_trash = [[INF for _ in range(M)] for _ in range(N)]
arround_trash = [[INF for _ in range(M)] for _ in range(N)]
 
arround_trash_can = [[0 for _ in range(M)] for _ in range(N)]
 
 
arr = []
start = []
flower = []
for x in range(N):
    temp = list(input())
    for y in range(M):
        if temp[y] == 'S':
            start = (x,y)
        elif temp[y] == 'F':
            flower = (x,y)
    
    arr.append(temp)
dx = [-1,1,0,0]
dy = [0,0,-1,1]
 
 
for x in range(N):
    for y in range(M):
        if arr[x][y] == 'g':
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if arr[nx][ny] == '.':
                        arround_trash_can[nx][ny] = 1
 
node_list = []
 
heapq.heappush(node_list,(0,0,start[0],start[1]))
 
step_trash[start[0]][start[1]] = 0
arround_trash[start[0]][start[1]] = 0
visited = [[True for _ in range(M)] for _ in range(N)]
 
while node_list:
    s_t,p_t,x,y = heapq.heappop(node_list)
 
    if not visited[x][y]:
        continue
    visited[x][y] = False
 
 
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<M:
            if arr[nx][ny] == 'g':
                if step_trash[nx][ny] > s_t + 1:
                    step_trash[nx][ny] = s_t + 1
                    arround_trash[nx][ny] = p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny], arround_trash[nx][ny], nx, ny))
            else:
                if step_trash[nx][ny] > s_t:
                    step_trash[nx][ny] = s_t
                    arround_trash[nx][ny] = p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny],arround_trash[nx][ny],nx,ny))
                elif step_trash[nx][ny] == s_t and arround_trash[nx][ny] > p_t + arround_trash_can[nx][ny]:
                    step_trash[nx][ny] = s_t
                    arround_trash[nx][ny] =  p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny],arround_trash[nx][ny],nx,ny))
 
 
 
 
 
 
x,y = flower
 
print(step_trash[x][y] , arround_trash[x][y])

이 문제를 지문을 이해하는데 어려움을 겪었던 문제였다. 

문제를 제대로 읽어야하는데 빈 공간을 갈때 주변의 쓰레기 개수와 상관없이 1개이든 4개이든 1번의 불쾌함으로 측정을 해야한다.

그러므로 이 점을 주의해서 우선순위를 설정을 해서 다익스트라를 해줘야한다.

다익스트라를 돌리기전에 사전 작업을 했는데, 쓰레기인 구역을 찾아서

그 주변에 빈공간이 있으면 arround_trash_can라는 배열에 1로 표시를 해줬다.

그래서 arround_trash_can이라는 배열에 0이 아닌 1이 표시된 부분은 쓰레기가 존재하는 옆칸을 지나가는 것이다.

이 문제에서 형택의 여자친구는 쓰레기를 지나가는 것을 가장 싫어하고, 쓰레기 옆을 지나가는 것을 두번째로 싫어한다고 되어있다.

그러므로 heapq에 우선순위를 쓰레기를 지나가는 것 s_t를 가장 앞에 두었고, 쓰레기 옆을 지나가는 개수인 p_t를 두번째 인자로 넣어주었다.

이렇게 한뒤 형택이 상하좌우로 움직이면서 쓰레기인 칸을 밟았을때에는 step_trash의 값과 비교를 해서 더 낮은 값이면, 갱신을 하고 넣어주었다.

그리고 빈공간일때에는 먼저 쓰레기를 밟는 개수가 더 작은 경우인지 확인을 한 뒤, 더 작으면 값을 갱신하고 heapq에 넣어준다.

근데 그게 아니라 쓰레기를 밟는 개수는 동일하다면, 쓰레기 옆을 지나간 횟수를 비교를 해서 heapq에 넣어준다.

이 문제에서 주의해야했던 점은 쓰레기 옆을 지나가는 유무를 구분하는 것이지, 빈공간 옆의 쓰레기의 개수를 세는

것이 아니였던 점이다.

import sys
import heapq
 
def dijkstra(flag=False,*arg):
    distance = [INF for _ in range(N+1)]
    distance[1] = 0
    node_list = []
    if flag:
        remove_node = arg[0]
    heapq.heappush(node_list,(0,1))
    
    while node_list:
        cur_dis,node = heapq.heappop(node_list)
        if cur_dis>distance[node]:
            continue
        for next_node in graph[node]:
            if flag and ((node,next_node) == remove_node or (next_node,node) == remove_node):
                continue 
            temp_distance = cur_dis + graph[node][next_node]
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(temp_distance,next_node))
    if not flag:
        stack = [(N,distance[N])]
        while stack:
            node,dis = stack.pop()
            for prev_node in graph[node]:
                if (prev_node,node) not in short_list:
                    if distance[prev_node] + graph[prev_node][node] == dis:
                        short_list.add((prev_node,node))
                        stack.append((prev_node,distance[prev_node]))
 
    return distance[N]
    
 
def input():
    return sys.stdin.readline()
 
 
N,M = map(int,input().split())
 
graph = [{} for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay
 
INF = float('inf')
 
short_list = set()
short_time = dijkstra()
short_list = list(short_list)
 
result = -1
for node in short_list:
    remove_time = dijkstra(True,node)
    result = max(result,remove_time - short_time)
 
print(result if result != INF else -1)

문제를 푸는 방식은 다음과 같다.

먼저 다익스트라로 최단 거리를 구한다.

그와 동시에 이동경로를 구해야한다.

즉 우리는 다익스트라를 하면서 누적된 이동거리 리스트를 이용해서 역산을 통해 최단 거리의 이동 경로를 구한다.

이렇게 구한 이동경로를 하나씩 검문을 하는 것이다.

그리고 그 검문을 했을때의 다익스트라를 구하고, 이 때의 최대값을 구하고, 지연된 시간을 구하면 된다.

이 문제는 다익스트라를 통해 이동경로를 추적하고, 그 이동경로를 활용해서 풀 수 있는 문제였다.

import sys
from collections import defaultdict
import heapq
def input():
    return sys.stdin.readline().rstrip()
N,M = map(int,input().split())
 
 
 
graph = [defaultdict(list) for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y].append((pay,True))
    graph[y][x].append((pay,False))
 
 
node_list = []
INF = float('inf')
distance_list = [INF for _ in range(N+1)]
distance_list[1] = 0
heapq.heappush(node_list,(0,1,1,True))
result = []
 
while node_list:
    cur_dis, cur_node , parent_node , cur_flag = heapq.heappop(node_list)
    if cur_dis > distance_list[cur_node]:
        continue
    if cur_node != parent_node:
        if cur_flag:
            result.append((parent_node, cur_node))
        else:
            result.append((cur_node, parent_node))
    for next_node in graph[cur_node]:
 
 
        for pay,flag in graph[cur_node][next_node]:
            if cur_dis + pay < distance_list[next_node]:
                distance_list[next_node] = cur_dis + pay
                heapq.heappush(node_list,(distance_list[next_node], next_node , cur_node , flag))
    
print(len(result))
for row in result:
    print(*row)

처음으로 풀었던 방식이다. 문제의 출력을 입력에 주어진 간선으로 출력해야하는 줄 알고, 좀 복잡하게 풀었다.

이 문제를 처음 본 순간 MST 문제 인줄 알았는데, MST 문제는 아니였다.

1번 조건만 보고 모든 노드들이 연결되는 최소인줄 알고 MST인줄 알았는데,

2번 조건을 찬찬히 읽어보니 다익스트라 문제였다.

네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

그 2번 조건은 다음과 같다.

슈퍼컴퓨터를 기준으로 모든 컴퓨터들은 최소 시간을 보장해야한다.

즉 슈퍼컴퓨터를 기준으로 모든 노드들에 대한 최소 시간의 다익스트라를 구해야하는 문제이다.

이 점만 주의하면 일반적인 다익스트라 풀이와 동일하다.

import sys
from collections import defaultdict
import heapq
def input():
    return sys.stdin.readline().rstrip()
N,M = map(int,input().split())
 
 
 
graph = [defaultdict(list) for _ in range(N+1)]
 
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y].append(pay)
    graph[y][x].append(pay)
 
 
node_list = []
INF = float('inf')
distance_list = [INF for _ in range(N+1)]
distance_list[1] = 0
heapq.heappush(node_list,(0,1,1))
result = []
 
while node_list:
    cur_dis, cur_node , parent_node  = heapq.heappop(node_list)
    if cur_dis > distance_list[cur_node]:
        continue
    if cur_node != parent_node:
        result.append((parent_node, cur_node))
    for next_node in graph[cur_node]:
 
 
        for pay in graph[cur_node][next_node]:
            if cur_dis + pay < distance_list[next_node]:
                distance_list[next_node] = cur_dis + pay
                heapq.heappush(node_list,(distance_list[next_node], next_node , cur_node ))
 
print(len(result))
 
for row in result:
    print(*row)

개선한 풀이이다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
 
N,M = map(int,input().split())
 
 
arr = [list(input()) for _ in range(N)]
 
sand_deque = deque()
 
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]
for x in range(N):
    for y in range(M):
        if not arr[x][y].isdigit():
            sand_deque.append((x,y))
        else:
            arr[x][y] = int(arr[x][y])
 
 
 
time = 0
 
while True:
    remove_sand = deque()
 
    while sand_deque:
        x,y = sand_deque.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0<=nx<N and 0<=ny<M):continue
            if arr[nx][ny] != '.':
                arr[nx][ny] -= 1
                if arr[nx][ny] == 0:
                    remove_sand.append((nx,ny))
                    arr[nx][ny] = '.'
    if remove_sand:
        sand_deque.extend(remove_sand)
        time += 1
    else:
        break
 
print(time)

처음에 dict을 이용해서 날먹할려다가 시간초과가 났던 문제이다.

문제를 푸는 방식은 다음과 같다. 모든 모래들은 하나의 큐에 넣은 뒤에, 8방향의 모래가 아닌곳의 개수를 -1씩 해준다.

그러면서 0이 되면, remove_sand라는 큐에 넣어준다.

그러면 이 모래성이 더이상 무너지지 않는 경우는 remove_sand가 비어있을때이다.

그래서 remove_sand가 비어있으면 break를 해주고, 있을때에는 sand_deque에 extend 해주고 그 때 time을 1 늘려준다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
 
def bfs(queue):
    dx = [-1,0,1,-1,1,-1,0,1]
    dy = [-1,-1,-1,0,0,1,1,1]
    while queue:
        x,y,cnt = queue.popleft()
 
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if not(0<=nx<N and 0<=ny<M):continue
            if arr[nx][ny]:
                arr[nx][ny] -= 1
                if not arr[nx][ny]:
                    queue.append((nx,ny,cnt+1))
 
    return cnt
 
N,M = map(int,input().split())
 
 
arr = [list(input()) for _ in range(N)]
 
 
sand_deque = deque()
for x in range(N):
    for y in range(M):
        if arr[x][y].isdigit():
            arr[x][y] = int(arr[x][y])
        else:
            arr[x][y] = 0
            sand_deque.append((x,y,0))
 
 
 
print(bfs(sand_deque))

 이 코드는 좀 더 깔끔한 방식으로 코드를 바꾼 방식이다.

원리 자체는 똑같다.    

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()
 
 
def dfs(cur_idx,parent_idx):
    global cnt
    depth[cur_idx] = depth[parent_idx] + 1
 
 
    if tree[cur_idx][0] != -1:
        dfs(tree[cur_idx][0],cur_idx)
    cnt += 1
    width[depth[cur_idx]].append(cnt) 
    if tree[cur_idx][1] != -1:
        dfs(tree[cur_idx][1],cur_idx)
 
N = int(input())
root_check = [0 for _ in range(N+1)]
tree = [[-1 -1] for _ in range(N+1)]
depth = [0 for _ in range(N+1)]
width = defaultdict(list)
for _ in range(N):
    x,left_node,right_node = map(int,input().split())
    tree[x] = [left_node,right_node]
    if left_node != -1:
        root_check[left_node] += 1
    if right_node != -1:
        root_check[right_node] += 1
root_num = -1
for k in range(1,N+1):
    if root_check[k] == 0:
        root_num = k
        break
 
 
cnt = 0
dfs(root_num,0)
 
max_value = 0
max_depth = -1
for d in range(1,max(depth)+1):
    max_width,min_width = max(width[d]),min(width[d])
    if max_value < max_width - min_width + 1:
        max_value = max_width - min_width + 1
        max_depth = d
 
print(max_depth,max_value)

이 문제를 풀때 주의할점은 2가지이다.

루트노드가 꼭 1인것은 아니다.

들어오는 순서가 1,2,3,4,5,6,7,8,....N이 아닐수도 있다.

이 2가지를 주의하면 풀면 되는 문제이다.

먼저 트리를 위한 (N+1)*2의 배열을 만들어뒀다.

각 행의 0번인덱스는 왼쪽 자식, 1번인덱스는 오른쪽자식을 의미한다.

이 문제는 중위순회를 구현을 해서, 왼쪽 자식->루트->오른쪽자식 순서로 탐색을 해준다.

그리고 루트일때 현재의 LEVEL에 width를 저장을 해주엇다.

cnt를 0부터 시작했기때문에, append 하기 직전에 +=1 을 해준것이다.

만약 1부터 하신분들은 순서를 바꾸면될것이다.

그리고 전체 레벨 만큼 탐색을하면서 최대 너비를 구해주면 되는 문제이다.

좀 더 깔끔히 하신분들은 level별로 2차원배열을 만든뒤에 둘 중 하나는 최대값 하나는 최소값을 저장을 시켜서 

마지막에 바로 계산이 가능하게 한 분들도 계신다.

import sys
from collections import deque
input = sys.stdin.readline
 
def bfs(red,blue):
    stack = deque()
 
    stack.append((*red,*blue,0))
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while stack:
        rx,ry,bx,by,dis = stack.popleft()
 
        for i in range(4):
            nrx,nry = rx,ry
            r_p = 0
            while 0<=nrx<N and 0<=nry<M and arr[nrx][nry] != '#' and arr[nrx][nry] != 'O':
                nrx += dx[i]
                nry += dy[i]
                r_p += 1
            nbx,nby = bx,by
            b_p = 0
            while 0<=nbx<N and 0<=nby<M and arr[nbx][nby] != '#' and arr[nbx][nby] != 'O':
                nbx += dx[i]
                nby += dy[i]
                b_p += 1
 
            if (nbx,nby) == (nrx,nry):
                if arr[nbx][nby] == 'O':
                    continue
                if r_p > b_p:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]
 
            elif arr[nbx][nby] == 'O':
                continue
            elif arr[nrx][nry] == 'O':
                return dis+1
            nrx -= dx[i]
            nry -= dy[i]
            nbx -= dx[i]
            nby -= dy[i]
            if not visited[nrx][nry][nbx][nby]:continue
            visited[nrx][nry][nbx][nby] = False
            stack.append((nrx,nry,nbx,nby,dis+1))
    return -1
 
N,M = map(int,input().split())
 
 
arr = []
blue = []
red = []
for x in range(N):
    temp = list(input())
    for y in range(M):
        if temp[y] == 'B':
            blue = (x,y)
        elif temp[y] == 'R':
            red = (x,y)
    arr.append(temp)
 
 
visited = [[[[True for _ in range(M)] for _ in range(N)] for _ in range(M)] for _ in range(N)]
 
 
result = bfs(red,blue)
print(result)

구슬 탈출의 마지막 시리즈다.

구슬탈출3에서 썼던 코드에서 경로추적이랑 10이상일때 종료인것만 제외시켜줬다.

구슬탈출1~4까지는 다 똑같은 코드이므로,

하나만 잘 풀어놓으면

코드를 1~3군데만 고쳐도 전부 통과할수 있다.