BFS미로찾기

n*n 크기의 미로를 갈 수 있는 곳은 1, 벽은 0으로 나타낸 상태에서 1,1에서 n,1까지의 최단거리를 구하는 문제.

 

DFS로 접근시 모든 경로를 계산하기 때문에 시간이 너무 오래걸림.

그렇기 때문에 BFS를 이용하는 것이 효율적.

 

from collections import deque
n= int(input())
li=[]
for _ in range(n):
	number = input()
	temp = [int(char) for char in number]
	li.append(temp)
	
visited=[[0]*n for _ in range(n)] 
result=[]
def bfs():
	
	queue=deque()
	queue.append((0,0,0))
	visited[0][0]=1
	
	while queue:
		x,y,dist=queue.popleft()
		
		if x==n-1 and y==n-1:
			return dist
		
		for dx, dy in [(1,0),(0,1),(-1,0),(0,-1)]:
			nx,ny=x+dx,y+dy
			
			if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and li[nx][ny] == 1:
				visited[nx][ny] = True
				queue.append((nx, ny, dist + 1))
		
	return -1
	

print(bfs())

 

아이디어는 상하좌우 방향에 대해 0또는 n번째 행/열 안쪽인지, 방문했었는지, 벽인지 통로인지를 if문으로 확인하여 모든 조건을 만족할 시 큐에 append하는것.

 

 

 

중급은 같은 형식의 미로에서 최소한의 방향전환으로 출구에 도달하는 횟수를 구하는 문제.

 

문제를 푸는 아이디어는 시작부터 방향전환 없이 이어지는 부분에 같은 값을 할당하고 이것을 큐에 넣은 다음 이 과정을 반복하여 목적지에 할당되는 값을 찾는다.

 

from collections import deque

MAX = 10000
n = int(input())
count = [[-MAX] * (n+2) for _ in range(n+2)]

for i in range(1, n+1):
    temp = input()
    for j in range(1, n+1):
        if temp[j-1] == '1':
            count[i][j] = MAX

 

n+2 * n+2 크기의 미로를 구현한다. 1은 10000으로 -1은 -10000으로 세팅한다.

q = deque()
q.append((1, 1)) # 시작점을 큐에 넣는다.
count[1][1] = -1 # 시작점은 일단 -1로 초기화한다.

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# 큐가 비었거나, 도착점에 도달했으면 루프를 빠져나간다.
while len(q) > 0 and count[n][n] == MAX:
	
    for i in range(n+2):
        print(count[i])
    print('----------------------------------------------------------------------')
    now_row, now_column = q.popleft()
    new_count = count[now_row][now_column] + 1

    for dr, dc in directions:
        r, c = now_row, now_column
        while True:
            r += dr
            c += dc
            # 계속 직진하다가 막히면 빠져나간다.
            # 현재의 회전 횟수보다
            # 더 작은 값이 들어가 있어도 빠져나간다. 
            if new_count > count[r][c]:
                break
            
            # 처음 도달한 곳이면 현재의 회전 횟수(c)를
            # 저장해주고, 그 위치를 큐에 넣는다.
            if count[r][c] == MAX:
                count[r][c] = new_count
                q.append((r, c))

 

초기 시작점을 -1로 초기화한다(시작점에서 이어지는 부분이 0번회전했다고 나타내기 위하여)

그 후 첫 문제와 같이 큐를 이용하되 한 방향으로 이동하는 것을 한번에 적용하기 위하여 while문을 사용한다.