백준 14497번 주난 의 난 [틀려서 3일후에 다시 볼것]

[시간초과 난 코드]

(궁시렁궁시렁) 잘 굴러가면 되는거 아니냐구  왜 안돼 ㅠㅠ

M, N = map(int, input().split())
x1, y1, x2, y2= map(int, input().split())
maps=[]
for col in range(M):
    maps.append(list(input()))



def solution(M,N, x1,y1, maps):
    move =[
    [0,1],
    [1,0],
    [0,-1],
    [-1,0]
]
    answer=0
    gg= True
    will_visit=[[x1-1, y1-1]]
    visited=[]
    while gg:
        answer+=1
        travel = will_visit[:]
        real_travel=[]
        # 0 까지의 세력 확장
        while travel:
            i= travel.pop()
            for m in move:
                flag = [i[0]+m[0],i[1]+m[1]]
                if( 0<=flag[0]<M )and (0<=flag[1]<N):
                     if maps[flag[0]][ flag[1]]=='0':

                        if flag not in will_visit:
                            travel.append(flag)
                            will_visit.append(flag)

        travel = will_visit[:]



        # 주난의 쿵
        next_count =[]
        for i in will_visit:
            if i in visited:
                continue
            else:
                visited.append(i)
                for m in move:
                    flag = [i[0]+m[0],i[1]+m[1]]
                    if( 0<=flag[0]<M )and (0<=flag[1]<N):
                            if maps[flag[0]][ flag[1]]=='0':
                                continue
                            elif maps[flag[0]][ flag[1]]=='#':
                                gg=False
                                return answer
                            else:
                                maps[flag[0]][ flag[1]]='0'
                                next_count.append(flag)

        will_visit=next_count

print(solution(M,N, x1,y1, maps))    

hello70825.tistory.com/75

를 참고했다.

---

주난이 상하좌우, 대각선을 이동할 수 있다고 가정할때, 친구가 있는 곳 까지 이동하는데 1초가 걸리고, 빈공간이 있는 곳으로 이동하는데 0초가 걸린다고 생각하면 된다.

빈 공간으로 이동할때는 appendleft 로 큐의 맨 왼쪽으로 넣어주고, 친구가 있는 곳으로 이동할때는 append 를 이용해 큐의 오른쪽으로 넣어준다. 

숨박꼭질3 과 유사한 문제라 heapq 를 이용해 풀어도된다함.

from collections import deque
n, m = map(int, input().split())
x1,y1,x2,y2= map(int, input().split())
D = [list(map(str, [*input()])) for _ in range(n)]
S =[[-1] *m for _ in range(n)]
q = deque()
q.append((x1-1, y1-1))
S[x1-1][y1-1] =0
dx,dy = [0,0,1,-1],[1,-1,0,0]

while q:
	x, y = q.popleft()
    for i in range(4):
    	nx,ny = x+dx[i] , y+dy[i]
        if 0<=nx<n and 0<=ny<m and S[nx][xy] ==-1:
        	if D[nx][ny]=='0':
            	q.appendleft((nx,ny))
                S[nx][ny] = S[x][y]
            else:
            	q.append((nx, ny))
                S[nx][ny] = S[x][y]+1
print(S[x2-1][y2-1])