Coding 공부

from collections import deque
def bfs(red,blue):
    stack = deque()

    stack.append((*red,*blue,0,''))
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    direction = ['U','D','L','R']
    while stack:
        rx,ry,bx,by,dis,route = stack.popleft()

        if dis >= 10:
            return (-1,'-')

        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,route + direction[i])
            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,route+direction[i]))
    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)
if result[0] != -1:
    print(result[0])
    print(result[1])
else:
    print(result[0])

 이 문제는 사실상 구슬탈출 2와 동일한 문제이다.

구슬 탈출2와 달라진점은 이동방향을 저장시키는 것외에는 없다.

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

먼저 방문배열을 4차원 배열로 만들어준다.

그 이유는, 빨간색공이 안 움직이지만, 파란공만 움직이는 경우도 있고,

파란공만 움직이고, 빨간공이 움직이지 않을때가 있으므로, 구분을 하기위해 4차원 배열을 선언을 해주었다.

그리고 BFS를 하는 과정은 다음과 같다. 한 방향으로 정하고 각가 red ball과 blue ball을

구멍 혹은 벽을 만나기전까지 계속 굴려준다.

그러면 최종적으로 위치하곳은 벽 혹은 구멍일 것이다. 이 과정에서 각각의 움직이는 횟수도 세어주었다.

먼저 구멍에 빠졌는지 확인을 해주자.

파란공과 빨간공이 전부 빠졌다면, 이것은 패배한것이므로, 제외를 해주자.

그리고 파란공만 들어간거면 그것 또한 패배한 것이므로, 제외를 하자.

그리고 빨간공만 들어갔을때에는 그때는 이긴것이므로, 지금까지 누적된 이동경로를 반환을 해주면 된다.

그리고 두 공의 위치가 최종적으로 같다면, 둘중 먼저 해당지점에 먼저와있는지가 중요하다.

우리는 위에서 반복횟수를 세어주었다.

반복 횟수가 적다는것은 더 빨리 도착한 것이므로, 반복횟수가 많은 볼을 한칸 뒤로 빼준다.

이러한 작업을 다 마치고 나면 위에서 우리는 벽이나 구멍외에는 멈추지 않았다.

그러면 현재 볼들이 있는 위치는 벽일테니, 뒤로 한칸씩 동일하게 이동해준다.

이렇게 한뒤에, 우리가 방문하지 않은 곳이면 방문표시를하고 stack에 넣어주면 된다.

이 문제는 방문을 어떻게 할것인가, 그리고 공을 굴릴때 어떻게 한번에 끝까지 굴릴것인가. 그리고 같은 위치에

중첩됬을때 어떻게 해결하는지 중요한 문제였다.

from collections import deque
def find_passenger(start,K):
    stack = deque()
    stack.append((*start,K))
    visited = [[True]*N for _ in range(N)]
    visited[start[0]][start[1]] = False
    if passenger_arr[start[0]][start[1]] < 0:
        result = [start[0],start[1],K,passenger_arr[start[0]][start[1]]]
        passenger_arr[start[0]][start[1]] = 0
        return result

    candidate = []
    while stack:
        x,y,fuel = stack.popleft()
        if fuel < 0:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if passenger_arr[nx][ny] <=0 and visited[nx][ny]:
                    visited[nx][ny] = False
                    stack.append((nx,ny,fuel-1))
                    if passenger_arr[nx][ny] < 0:
                        candidate.append([nx,ny,fuel-1,passenger_arr[nx][ny]])
    if candidate:
        candidate.sort(key=lambda x : (-x[2],x[0],x[1]))
        result = candidate[0]
        passenger_arr[result[0]][result[1]] = 0
        return result
    else:
        return False

def find_destination(passenger):
    stack = deque()
    stack.append((passenger[0],passenger[1],passenger[2]))
    destination = destination_dict[passenger[-1]]
    visited = [[True]*N for _ in range(N)]
    visited[passenger[0]][passenger[1]] = False
    init_fuel = passenger[2]
    while stack:
        x,y,fuel = stack.popleft()
        if fuel <= 0:
            return False
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx <N and 0<=ny<N:
                if passenger_arr[nx][ny] <=0 and visited[nx][ny]:
                    visited[nx][ny] = False
                    stack.append((nx,ny,fuel-1))
                    if (nx,ny) == destination:
                        fuel = 2*init_fuel - fuel + 1
                        result = [nx,ny,fuel]
                        return result

N,M,K = map(int,input().split())

passenger_arr = [list(map(int,input().split())) for _ in range(N)]
destination_dict = {}
taxi = list(map(lambda x : x-1 ,map(int,input().split())))
ind = 2



dx = [-1,0,1,0]
dy = [0,-1,0,1]

for _ in range(M):
    start_x,start_y,end_x,end_y = map(lambda x : x-1 ,map(int,input().split()))
    passenger_arr[start_x][start_y] = -ind
    destination_dict[-ind] = (end_x,end_y)
    ind += 1


answer = 0
cnt = 0
while cnt <M:
    passenger = find_passenger(taxi,K)
    if not passenger:
        answer = -1
        break
    destination = find_destination(passenger)
    if not destination:
        answer = -1
        break
    taxi = [destination[0],destination[1]]
    K = destination[-1]
    if K < 0:
        answer = -1
        break
    cnt += 1


if answer == -1:
    print(answer)
else:
    print(K)

경로 중간에 fuel이 0이 되어도 false 반환 안되게 함

from collections import deque

def bfs(node):
    stack = deque()
    stack.append(node)

    while stack:
        node = stack.popleft()

        for next_node in graph[node]:
            if visited[next_node] == -1:
                visited[next_node] = visited[node] + 1

                stack.append(next_node)



N, M = map(int,input().split())
INF = float('inf')
visited = [-1]*(N+1)


visited[1] = 0

graph =[[] for _ in range(N+1)]


for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
bfs(1)

max_value = max(visited)
max_ind = -1
for k in range(1,N+1):
    if visited[k] == max_value:
        max_ind = k
        break
print(max_ind,max_value,visited.count(max_value))

import sys
from collections import deque
input = sys.stdin.readline

for _ in range(int(input())):
    M,N = map(int,input().split())
    arr = []
    sange = []
    fire_set = set()
    visited = [[True]*M for _ in range(N)]
    for x in range(N):
        input_list = list(input().strip())
        for y in range(M):
            if input_list[y] == '*':
                fire_set.add((x,y))
            elif input_list[y] == '@':
                sange.append((x,y))
                visited[x][y] = False
                input_list[y] = '.'
        arr.append(input_list)
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    times = 0
    result = 'IMPOSSIBLE'
    flag = False
    while sange:
        new_sange = []
        new_fire = set()
        for fire in fire_set:
            for i in range(4):
                nx = fire[0] + dx[i]
                ny = fire[1] + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if arr[nx][ny] == '.':
                        new_fire.add((nx,ny))
                        arr[nx][ny] = '*'
        for sa in sange:
            for i in range(4):
                nx = sa[0] + dx[i]
                ny = sa[1] + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if visited[nx][ny] and arr[nx][ny] == '.':
                        new_sange.append((nx,ny))
                        visited[nx][ny] = False
                else:
                    result = times+1
                    flag = True
                    break
        if flag:
            break
        times += 1
        sange = new_sange[:]
        fire_set = new_fire

    print(result)
                

import sys
from collections import deque
input = sys.stdin.readline

def bfs(stack):
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while stack:
        x,y = stack.popleft()
        flag = visited[x][y] if visited[x][y] != 'FIRE' else 'FIRE'
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if visited[nx][ny] == -1 and (arr[nx][ny] == '.' or arr[nx][ny] == '@'):
                    if flag == 'FIRE':
                        visited[nx][ny] = flag
                    else:
                        visited[nx][ny] = flag + 1
                    stack.append((nx,ny))
            else:
                if flag != 'FIRE':
                    return flag + 1
    return 'IMPOSSIBLE'





for _ in range(int(input())):
    M,N = map(int,input().split())
    stack = deque()
    arr = []
    visited = [[-1]*M for _ in range(N)]
    for x in range(N):
        input_list = input()
        for y in range(M):
            if input_list[y] == '*':
                stack.append((x,y))
                visited[x][y] = 'FIRE'
            elif input_list[y] == '@':
                start = (x,y)
                visited[x][y] = 0
        arr.append(input_list)
    stack.append(start)
    print(bfs(stack))

# # 1600 말이 되고픈 원숭이
from collections import deque
K = int(input())
W,H = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(H)]

stack = deque()
stack.append((0,0,0,K))

visited = [[[0 for z in range(K+1)] for y in range(W)] for _ in range(H)]
visited[0][0][0] = 1
horse_move = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]
move = [(-1,0),(1,0),(0,-1),(0,1)]
result = -1
while stack:
    x,y,cnt,horse_cnt = stack.popleft()
    if x+1 == H and y+1 == W:
        result = cnt
        break
    for dx,dy in move:
        nx = x + dx
        ny = y + dy
        if 0<=nx<H and 0<=ny<W:
            if not arr[nx][ny]:
                if not visited[nx][ny][horse_cnt]:
                    stack.append((nx,ny,cnt+1,horse_cnt))
                    visited[nx][ny][horse_cnt] = 1
    if horse_cnt:
        for dx,dy in horse_move:
            nx = x + dx
            ny = y + dy
            if 0<=nx<H and 0<=ny<W:
                if not arr[nx][ny]:
                    if not visited[nx][ny][horse_cnt-1]:
                        stack.append((nx,ny,cnt+1,horse_cnt-1))
                        visited[nx][ny][horse_cnt-1] = 1



print(result)

이 문제는 두가지의 이동방식이 있고, 그것을 구분해서 BFS를 해주면 된다. 하지만 여기서 주의할 점은 다음과 같다.

방문 표시를 체크를 하는데 주의를 해야한다.

1

4 4

0 0 0 0

0 0 0 0

0 0 1 1

0 0 1 0

위와 같이 되어 있다고 했을시, 방문표시를 따로 구분하지 않고 한가지로 했을시에는, 말로 왔는지, 원숭이로 왔는지 정확히 모르기 때문에 원하는 답이 안나올 수 있다.

그래서 visitied를 기존의 x,y 좌표 뿐만아니라 말의 이동회수를 기준까지 포함해서, 방문표시를 해주었다. 이부분만 조심해주면, 문제를 풀 수 있다.