ABC 348 D번 복기 - 그래프를 재구성하고 BFS/DFS를 해야하는 문제

https://atcoder.jp/contests/abc348/tasks/abc348_d

D - Medicines on Grid

 

 

문제 자체는 어디서나 많이 보던 기본적인 BFS/DFS 셋팅이다

 

2차원 맵에 특정 위치에 약이 있는데, 이 약을 먹으면 에너지가 E로 된다.

 

이동할때마다 에너지가 1씩 감소한다

 

약은 먹어도 되고 먹지 않아도 되는데, 단 1번만 먹을 수 있고 먹으면 사라진다

 

에너지 0부터 시작한다고 할때, 목표로 하는 지점에 도착할 수 있는가?

 

그냥 기본적인 BFS처럼 출발지점에서 시작해서,

 

약이 있는지 먼저 체크해보고 약을 먹을때 에너지가 커지면 약을 먹고 방문체크해주고

 

에너지가 양수이면 다음 위치로 이동

 

다음 위치로 이동할때는 어차피 에너지가 0이면 이동을 못하는 것이기 때문에 이동에 대해서는 방문체크는 필요없고

 

약을 먹었냐 안먹었냐로 방문체크를 하는데... 매 큐의 원소마다 방문체크를 해줘야해서  

 

(시간초과날것 같긴 했지만..이것 말고는 없는것 같아서 )visited를 복사하다보니 시간초과가 나는것 같더라

 

from collections import deque
from sys import stdin

def bfs(x,y,p,q,h,w,maps,med):

    queue = deque([(x,y,0,[0]*(n))])

    while queue:
        
        x,y,e,visited = queue.popleft()

        f = False

        if med[y][x] != 0:
            
            if visited[med[y][x][1]] == 0:
                
                if e < med[y][x][0]:
                    
                    e = med[y][x][0]
                    dvisited = visited[:]
                    dvisited[med[y][x][1]] = 1
                    f = True
        
        if e > 0:
            
            for a,b in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                dx = x + a
                dy = y + b

                if dx >= 0 and dx <= w-1 and dy >= 0 and dy <= h-1 and maps[dy][dx] != '#':
                    
                    if dx == p and dy == q:
                        
                        return True
                    
                    if f:

                        queue.append((dx,dy,e-1,dvisited))
                    
                    else:
                        
                        queue.append((dx,dy,e-1,visited))
    
    return False
                
h,w = map(int,stdin.readline().split())

maps = [list(stdin.readline().rstrip()) for _ in range(h)]

for y in range(h):
    
    for x in range(w):
        
        if maps[y][x] == 'S':
            
            s_x = x
            s_y = y
        
        elif maps[y][x] == 'T':
            
            t_x = x
            t_y = y

n = int(stdin.readline())

med = [[0]*w for _ in range(h)]

for i in range(n):
    
    r,c,e = map(int,stdin.readline().split())

    med[r-1][c-1] = (e,i)

if bfs(s_x,s_y,t_x,t_y,h,w,maps,med):
    
    print('Yes')

else:
    
    print('No')

 

 

 

BFS하면서 큐 안에 visited를 넣으면 visited를 복사하다보니 시간초과나니까 피해야한다는건 아는데

 

그래도 이것 말고는 없는것 같아서리

 

그래서 visited 복사 안하는 DFS로 바꿨는데 그래도 시간초과나더라?

 

from sys import stdin

def dfs(x,y,e,p,q):
    
    if x == p and y == q:
        
        return True
    
    eat = False

    if med[y][x] != 0:
            
        if visited[med[y][x][1]] == 0:
                
            if e < med[y][x][0]:
                    
                e = med[y][x][0]
                visited[med[y][x][1]] = 1
                eat = True
                    
    if e > 0:
        
        for a,b in [[0,1],[1,0],[0,-1],[-1,0]]:
            
            dx = x + a
            dy = y + b

            if dx >= 0 and dx <= w-1 and dy >= 0 and dy <= h-1 and maps[dy][dx] != '#':
                
                f = dfs(dx,dy,e-1,p,q)

                if f:
                    
                    return True

                if eat:

                    visited[med[y][x][1]] = 0

    return False
                
h,w = map(int,stdin.readline().split())

maps = [list(stdin.readline().rstrip()) for _ in range(h)]

for y in range(h):
    
    for x in range(w):
        
        if maps[y][x] == 'S':
            
            s_x = x
            s_y = y
        
        elif maps[y][x] == 'T':
            
            t_x = x
            t_y = y

n = int(stdin.readline())

med = [[0]*w for _ in range(h)]

for i in range(n):
    
    r,c,e = map(int,stdin.readline().split())

    med[r-1][c-1] = (e,i)

visited = [0]*n

if dfs(s_x,s_y,0,t_x,t_y):
    
    print('Yes')

else:
    
    print('No')

 

 

 

방법을 조금 바꿔서, 매 이동마다 에너지가 1씩 감소하기 때문에 핵심적으로 이동해야할 위치는

 

시작점, 약의 위치, 도착점들이다.

 

시작점, 약의 위치, 도착점을 하나의 노드로 보고 노드 i에서 존재하는 약만을 사용했을때 에너지 e로 

 

다른 노드 j로 최단거리로 이동할 수 있는지 체크해서 이동할 수 있다면 i에서 j로 가는 간선이 존재한다고 본다

 

첫 시작에 에너지가 0이기 때문에 시작점에 약이 없으면 어차피 도착점으로 못간다

 

도착점에는 약이 없을수도 있는데 약이 없다면 에너지가 0인 노드로 만들고 약이 있으면 해당 에너지의 노드로 만들고..

 

근데 A - B - C로 연결이 되어있다고 하지만, A > C로 B의 약을 먹지 않고 바로 갈수도 있는데?

 

근데 중요한건 시작점에서 도착점까지 최단거리를 요구하는게 아니고, 도착할 수 있느냐 아니냐가 핵심이다

 

이동할때마다 에너지가 1씩 감소하는데, 에너지를 보충할 수 있는 수단은 약이 있는 위치

 

그래서 약이 있는 위치로 이동하면서 도착점까지 이동하는게 가장 유리하다 이거지

 

이렇게 그래프 만들기만 한다면, visited 처리하면 약을 1번만 먹는다라는 조건을 지키면서...

 

애초에 A노드에서 B노드 간선이 있다는건 A에서 약을 먹고 B로 무조건 갈 수 있으며 A는 방문처리 하니까 다시 안갈거고

 

그래서 약에 대한 조건은 더 이상 고려할필요가 없어진다

 

이 방법을 생각은 했는데... 뭔가 더 고려해야하는거 아닌가??

 

i번에서만 약을 먹고 다른 노드들로 갈 수 있으면 i에서 j로 간선이 있다...

 

하지만 i번에서 약을 먹고 k번에서도 약을 먹고 j로 갈수 있으면 i에서 j로 간선이 있다 이런것도 고려해야하나?? 

 

이런 복잡한 생각 하다가 시도하지 않았던게 아쉽다..

 

냉정하게 생각했으면 시도할만했는데...

 

틀려도 그냥 패널티 받고 말지... 하는 마음으로 가볍게 시도해보는게 좋은것 같아 중요한 대회도 아니고

 

from collections import deque
from sys import stdin

def bfs1(x,y,e,i):
    
    queue = deque([(x,y,e)])
    visited = [[0]*w for _ in range(h)]
    visited[y][x] = 1

    while queue:
        
        x,y,e = queue.popleft()

        if e > 0:

            for a,b in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                dx = x + a
                dy = y + b

                if dx >= 0 and dx <= w-1 and dy >= 0 and dy <= h-1 and visited[dy][dx] == 0 and maps[dy][dx] != '#':
                    
                    if e-1 >= 0:
                        #에너지가 남아있을때, 약이 있는 위치에 이동할 수 있기만 한다면..
                        if med.get((dx,dy),0) != 0:
                            
                            graph[i].append(med[(dx,dy)][1])

                        queue.append((dx,dy,e-1))
                        visited[dy][dx] = 1

h,w = map(int,stdin.readline().split())

maps = [list(stdin.readline().rstrip()) for _ in range(h)]

#시작점, 도착점 찾기
for y in range(h):
    
    for x in range(w):
        
        if maps[y][x] == 'S':
            
            s_x = x
            s_y = y
        
        elif maps[y][x] == 'T':
            
            t_x = x
            t_y = y

n = int(stdin.readline())

med = {}

#모든 약의 위치를 찾기
s = -1 #시작점에 약이 있는가?
t = -1 #도착점에 약이 있는가?

for i in range(n):
    
    r,c,e = map(int,stdin.readline().split())

    if s_x == c-1 and s_y == r-1:
        
        s = i 
    
    if t_x == c-1 and t_y == r-1:
        
        t = i

    med[(c-1,r-1)] = (e,i)

if s == -1: #S = -1이면 시작점에 약이 없으니..
    
    print('No')

else:
    
    m = n

    if t == -1: #도착점에 약이 없는 경우...
        
        med[(t_x,t_y)] = (0,n)
        m = n+1
        t = n
    
    graph = [[] for _ in range(m)]
    
    #m개의 약 노드들에서, i번째 위치에서 먹은 약만으로
    #다른 노드로 갈 수 있는가?
    for x,y in med.keys():
        
        e,i = med[(x,y)]

        if e > 0:
            
            bfs1(x,y,e,i)

 

 

이렇게 새로 만든 그래프에서 시작점 노드에서 BFS를 다시 수행해서 도착점으로 갈 수 있는지 체크하면 된다

 

def bfs2(s,t,m,graph):
    
    queue = deque([s])

    visited = [0]*m
    visited[s] = 1

    while queue:
        
        s = queue.popleft()

        for v in graph[s]:
            
            if visited[v] == 0:
                
                if v == t:
                    
                    return True

                queue.append(v)
                visited[v] = 1
    
    return False
    
#그래프를 만들고, 해당 그래프 위에서
    #시작점에서 끝점으로 도달할 수 있는지 BFS
    if bfs2(s,t,m,graph):
        
        print('Yes')
    
    else:
        
        print('No')