🏆Today Code Test

🛠Problem Approach

문제

동민이는 NxM 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러마리 괴물이 있어 이를 피해탈출해야 한다. 동빈이의 위치는 (1,1)이고, 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이 때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다.

미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때, 동민이가 탈출하기 위해 움직여야하는 최소 칸의 개수는? 칸을 셀 때는 마지막 칸과 시작칸 모두 포함한다.

• 입력조건
  • 4≤ N, M ≤200
  • 공백없이 미로 값 입력
  • 시작 칸과 마지막 칸은 항상 1

✅ 최소거리를 구하는 과정이라 BFS를 사용 → 도착시, 바로 종료가 가능해서 유리

🙄 문제 : 최소거리를 측정하는데 필요 없는 곳을 조사할 때, count를 하는 문제

내 풀이

from collections import deque

n, m = map(int, input().split())
maze = [[int(i[j])for j in range(m)] for i in [input() for _ in range(n)]]
queue = deque()
visited = [[False if i[j] == 1 else True for j in range(m)] for i in maze]

cnt = 1
dr = [0,1,-1,0]
dc = [1,0,0,-1]

# 시작 위치 방문 및 큐 삽입
queue.append((0,0))
visited[0][0] = True

# bfs 시작
while queue:
    cur = queue.popleft()
    r, c = cur[0], cur[1]

    for i in range(len(dr)):
        nr = r + dr[i]
        nc = c + dc[i]
        if nr < 0 or nr >= n or nc < 0 or nc >= m:
            continue
        if maze[nr][nc] == 1 and not visited[nr][nc]: # 1이거나 미방문이면
            queue.append((nr,nc))
            visited[nr][nc] = True
            cnt += 1
            print("이프문 들어간다 후",nr,nc, '->', cnt)

            if nr == n-1 and nc == m-1: # 도착지에 도착하면 멈춤
                break
    if nr == n-1 and nc == m-1:
        break

    print("리얼현재",nr,nc, '->', cnt)

print(cnt)

🔑Solution

KEY

🌳 BFS는 시작 지점에서 가까운 노드부터 차례로 그래프의 모든 노드를 탐색한다.

🌳 모든 노드의 거리가 1로 동일하므로 모든 노드의 최단 거리값을 기록하면 해결 가능

from collections import deque

def bfs(x, y):
	queue = deque()
	queue.append((x,y))
	while queue: # 큐가 빌 때까지 반복
		x, y = queue.popleft()
		# 현재 위치에서 상, 하, 좌, 우 확인
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			
			# 미로공간 벗어낫는가?
			if nx < 0  or nx >= n or ny < 0 or ny >=m:
					continue

			# 괴물이 존재하는가?
			if graph[nx][ny] == 0:
					continue

			# 방문하지 않은 곳인가?
			if graph[nx][ny] == 1:
					graph[nx][ny] = graph[x][y] + 1 # 직전보다 한 노드 더 이동했으므로 -> 최단거리저장
					queue.append((nx,ny)) # 움직인 좌표 큐에 삽입
	return graph[n-1][m-1] # 마지막 위치까지의 최단 거리 반환

n, m = map(int, input().split())
graph = [[int(i[j])for j in range(m)] for i in [input() for _ in range(n)]]

dx = [-1,1,0,0]
dy = [0,0,-1,1]

print(bfs(0,0))

🐾 그래프에 직접 최소거리 저장하는 스킬