백준 2178

📚오늘의 공부📚

✅ 백준 2178

문제

나의 풀이(틀림)

이번 문제는 최단거리를 찾아내는 문제였다. 우선 길이 아닌곳에는 모두 0을 추가해서 지정된 길을 벗어날 수 없도록 하였고, bfs를 활용해 풀려고 하였다. 하지만 풀다보니 모든 경우의 수를 구해버렸고 나중에 다른 길로 간 경우를 찾아서 빼려고 했지만 쉽지않았다.

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
maze = []
for i in range(n + 2):
    if i == 0:
        maze.append([0] * (m + 2))

    elif i == (n + 1):
        maze.append([0] * (m + 2))

    else:
        maze.append([0] + list(map(int, sys.stdin.readline().strip())) + [0])


# 너비 우선 탐색
def bfs(x, y, n, m):
    count = 0

    queue = deque()
    queue.append((y, x))

    while queue:
        if x == n and y == m:
            return count

        y, x = queue.popleft()
        # 오른쪽
        if maze[y][x + 1] == 1:
            count += 1
            print("right", count)
            queue.append((y, x + 1))

        # 위로
        if maze[y + 1][x] == 1:
            count += 1
            print("down", count)
            queue.append((y + 1, x))

        # 왼쪽
        if maze[y][x - 1]:
            count += 1
            print("left", count)
            queue.append((y, x - 1))

        # 아래로
        if maze[y - 1][x]:
            count += 1
            print("up", count)
            queue.append((y - 1, x))

        maze[y][x] = 0

    return count


bfs(1, 1, n + 1, m + 1)

input

4 6
101111
101010
101011
111011

output

down 1
down 2
down 3
right 4
right 5
up 6
up 7
up 8
right 9
right 10
right 11
down 12
down 13
right 14
down 15
down 16
right 17

🎯하루 회고🎯

백준 2178을 푸는과정에서 한번 잘못된 길로 갔다니 계속 꼬여서 이상한길로 갔던거 같다. 내일 이문제를 다시 풀면서 분석해보는 시간을 가져야겠다.