[백준]1261:알고스팟

BFS

문제 : 알고스팟
시간 제한이 1초라서 가지치기가 필수적인데 가지치기로도 시간이 부족했다.
이 문제의 핵심은 deque 의 appendleft 를 사용하는 것!
방문한 곳은 다시 방문 안할 것이기 때문에 처음부터 가장 작은수를 넣어주는 것이 중요하다.
그래서 중복 방문 된 곳의 값을 최소화 하기 위해 벽이 없는 0 부터 큐에 넣어주는 것이다.

핵심 코드:

if graph[nx][ny] == 1 and visited[nx][ny] == INF:
	visited[nx][ny] = visited[x][y]+1
	q.append((nx, ny))
elif graph[nx][ny] == 0 and visited[nx][ny] == INF:
	visited[nx][ny] = visited[x][y]
	q.appendleft((nx, ny))

다른 분들의 풀이도 봤는데 다 appendleft로 풀었다.
이 문제는 appendleft 말고는 시간 초과 때문에 힘들듯.. ㅋ

정답코드

import sys
from collections import deque
input = sys.stdin.readline
m, n = map(int, input().split())
graph= []
for i in range(n):
	graph.append(list(map(int,sys.stdin.readline().rstrip())))
INF = int(1e9)
visited = [[INF]* m for _ in range(n)]
visited[0][0] = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
	q = deque()
	q.append((0, 0))
	while q:
		x, y = q.popleft()
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if nx < 0 or ny < 0 or nx >= n or ny >= m:
				continue
			if visited[nx][ny] != INF and visited[nx][ny] <= visited[x][y]+1:
				continue
			if graph[nx][ny] == 1 and visited[nx][ny] == INF:
				visited[nx][ny] = visited[x][y]+1
				q.append((nx, ny))
			elif graph[nx][ny] == 0 and visited[nx][ny] == INF:
				visited[nx][ny] = visited[x][y]
				q.appendleft((nx, ny))
	return visited[n-1][m-1]
print(bfs())

시간초과 난 코드

import sys
from collections import deque
input = sys.stdin.readline
m, n = map(int, input().split())
graph= []
for i in range(n):
	graph.append(list(map(int,sys.stdin.readline().rstrip())))
INF = int(1e9)
visited = [[INF]* m for _ in range(n)]
visited[0][0] = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
	ret = INF
	q = deque()
	q.append((0, 0))
	while q:
		x, y = q.popleft()
		if x == n-1 and y == m-1:
			ret = min(ret, visited[x][y])
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if nx < 0 or ny < 0 or nx >= n or ny >= m:
				continue
			if visited[nx][ny] != INF and visited[nx][ny] < visited[x][y]+1:
				continue
			if graph[nx][ny] == 1:
				visited[nx][ny] = visited[x][y]+1
				q.append((nx, ny))
			elif graph[nx][ny] == 0:
				visited[nx][ny] = visited[x][y]
				q.append((nx, ny))
	return ret
print(bfs())