[Algorithm🧬] 백준 3055 : 탈출

문제

1. 홍수 BFS -> 화가 BFS

Memory Limit Exceed

원래는 홍수는 * 로만 체크하고 ch 배열을 따로 안두려고 했는데,

• 로 체크하니까 계속 다 체크되어버려서..
  ch 배열 만들어서 몇초에 그 칸까지 침범하는지를 표시.

홍수를 하나 바꾸고,
cnt 가 바뀌는 순간이 한칸 이동해서 다음 걸로 가는 순간일테니까
그 바뀌는 순간에 다시 홍수를 나게 하는 방식으로 진행했다.

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

def 홍수(x, y, cnt):
    for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        nx, ny = x + dx, y + dy

        # 방문 체크.
        # 이미 홍수가 났으면 방문 X
        if bmap[nx][ny] == '*':
            continue

        # 벽이나 비버 집도 방문 X
        if bmap[nx][ny] == 'X' or bmap[nx][ny] == 'D':
            continue

        # 상하좌우를 * 로 만들고
        bmap[nx][ny] = '*'
        # 방금 홍수난 곳을 다음에 방문할 수 있게 표시.
        ch[nx][ny] = cnt + 1



def BFS(i, j):

    # 갈 수 있는 곳 : 빈 곳 . 화가 S
    # 갈 수 없는 곳 : 홍수 * 바위 X 방문 ,
    # 종료 조건 : 비버 D 
    q = deque([(i, j, 0)])
    bmap[i][j] = ','

    bcnt = -1

    while q:
        x, y, cnt = q.popleft()

        # print(x, y, cnt)
        if bmap[x][y] == 'D':
            return cnt

        # cnt 가 달라짐 -> 홍수 하나 움직임 -> 화가 하나 움직임.
        if bcnt < cnt:
            bcnt = cnt
            for i in range(R + 2):
                for j in range(C + 2):
                    # 맨 마지막에 홍수가 추가된 위치에서만 상하좌우 홍수로 넓히면 좋겠음
                    # ch 배열에 맨 마지막 순서 cnt + 1로 기록해서 다음 순서에 처리할 수 있게하자.
                    if ch[i][j] == cnt and bmap[i][j] == '*':
                        홍수(i, j, cnt)

        # for i in range(R + 2):
        #     print(bmap[i], ch[i])


        for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            nx, ny, ncnt = x + dx, y + dy, cnt + 1

            if bmap[nx][ny] == ',':
                continue
            
            # 홍수, 바위로는 갈 수 없음.
            if bmap[nx][ny] == '*' or bmap[nx][ny] == 'X':
                continue

            
            if bmap[x][y] == 'D':
                return ncnt
            bmap[nx][ny] == ','
            q.append((nx, ny, ncnt))
            

            # print((nx, ny, ncnt))

    
    return -1
    

# T = int(readl())
# for _ in range(T):
R, C = map(int, readl().split())
bmap = [['X'] + [c for c in readl().rstrip()] + ['X'] if 1 <= i <= R else ['X'] * (C + 2) for i in range(R + 2)]


for i in range(R + 2):
    if 'S' in bmap[i]: # 화가
        ax, ay = i, bmap[i].index('S')
        break

# 화가도 움직이고 홍수(지도 자체를 바꾸면 됨)도 움직임.
ch = [[0] * (C + 2) for _ in range(R + 2)]
b = BFS(ax, ay)
print(b if b != -1 else "KAKTUS")

메모리 초과가 나서

힌트를 보고 변경.
둘 다 큐에 넣는데, 큐의 길이만큼 돌려주면 되는거였다......
그리고도 시간 초과가 나서 time 조건 추가.

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



def BFS():

    # 갈 수 있는 곳 : 빈 곳 . 화가 S
    # 갈 수 없는 곳 : 홍수 * 바위 X 방문 ,
    # 종료 조건 : 비버 D 
    q = deque()

    for i in range(R + 2):
        for j in range(C + 2):
            if bmap[i][j] == 'S':
                q.append((i, j))
                time[i][j] = 0
                bmap[i][j] = ','

            if bmap[i][j] == '*':
                floodq.append((i, j))

    cur = 0
    while q:
        # 홍수 먼저 * 로 채우고,
        for i in range(len(floodq)):
            x, y = floodq.popleft()

            for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy

                # 방문 체크.
                # 이미 홍수가 났거나 벽이나 비버 집 -> 방문 X
                if bmap[nx][ny] == 'X' or bmap[nx][ny] == '*' or bmap[nx][ny] == 'D':
                    continue

                # * 로 만들고
                bmap[nx][ny] = '*'
                # 방금 홍수난 곳을 다음에 방문할 수 있게 큐에 넣는다.
                floodq.append((nx, ny))

                
        # for i in range(R + 2):
        #     print(bmap[i], ch[i])

        # 비버굴을 찾아서 이동!!
        for _ in range(len(q)):
            x, y = q.popleft()

            for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy

                # 홍수, 바위로는 갈 수 없음.
                if bmap[nx][ny] == '*' or bmap[nx][ny] == 'X':
                    continue

                # 이전에 거기 간 시간이 더 짧다면 갈 수 없음.
                if time[nx][ny] <= time[x][y] + 1:
                    continue
                
                # 비버 굴이면 시간 return
                if bmap[nx][ny] == 'D':
                    return time[x][y] + 1

                # 시간 갱신
                time[nx][ny] = time[x][y] + 1
                q.append((nx, ny))

    return -1
    

# T = int(readl())
# for _ in range(T):
R, C = map(int, readl().split())
bmap = [['X'] + [c for c in readl().rstrip()] + ['X'] if 1 <= i <= R else ['X'] * (C + 2) for i in range(R + 2)]


# 화가도 움직이고 홍수(지도 자체를 바꾸면 됨)도 움직임.
floodq = deque()

time = [[0] + [R * C + 1] * C + [0] if 1 <= i <= R else [0] * (C + 2) for i in range(R + 2)] # 화가 시간 체크

b = BFS()
print(b if b != -1 else "KAKTUS")