백준 2178

 

처음에 시도한 코드(실패)

from collections import deque

n, m = map(int, input().split())
map_data = [list(map(int, input())) for m in range(n)]
print(map_data)

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


def bfs(x, y):
  queue = deque()
  queue.append([x, y])
  count = 1
  while queue:
    queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx > m or ny > n:
        continue
      if map_data[nx][ny] == 1:
        queue.append([nx, ny])
        count += 1
      if [n, m] in queue:
        return count
      return float('inf')


counts = []
for i in range(n):
  for j in range(m):
    if map_data[i][j] == 1:
      counts.append(bfs(i, j))

print(min(counts))

 

수정한 코드(실패)

from collections import deque

n, m = map(int, input().split())
map_data = [list(map(int, input())) for _ in range(n)]

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


def bfs(x, y):
    queue = deque()
    queue.append([x, y])
    count = 1
    while queue:
        x, y = queue.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 map_data[nx][ny] == 1:
                queue.append([nx, ny])
                map_data[nx][ny] = 0  # 방문한 위치는 0으로 변경
                count += 1
                if nx == n-1 and ny == m-1:  # (n, m)에 도착한 경우
                    return count
    return -1  # (n, m)에 도착하지 못한 경우


counts = []
for i in range(n):
    for j in range(m):
        if map_data[i][j] == 1:
            counts.append(bfs(i, j))

print(min(counts))

 

최종 코드

from collections import deque

n, m = map(int, input().split())
map_data = [list(map(int, input())) for _ in range(n)]

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


def bfs(x, y):
    queue = deque()
    queue.append([x, y, 1])  # 시작 노드의 최단 거리는 1
    while queue:
        x, y, distance = queue.popleft()
        if x == n-1 and y == m-1:  # (n, m)에 도착한 경우
            return distance
        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 map_data[nx][ny] == 1:
                queue.append([nx, ny, distance+1])  # 노드 추가 시 최단 거리 기록
                map_data[nx][ny] = 0  # 방문한 노드는 0으로 변경
    return -1  # (n, m)에 도착하지 못한 경우


print(bfs(0, 0))