[백준][파이썬]2178번: 미로탐색

2178번: 미로 탐색

문제 출처 : https://www.acmicpc.net/problem/2178

---

내 풀이 (틀렸습니다)

from collections import deque

n, m = map(int, input().split())

map_ = []
for i in range(n):
    map_.append(list(map(int, input())))

def bfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    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:
                if map_[nx][ny] == 1:
                    map_[nx][ny] = map_[x][y] + 1
                    queue.append((nx, ny))
    return map_[-1][-1]

print(bfs(0, 0))

---

내 풀이 (성공)

from collections import deque

n, m = map(int, input().split())

map_ = []
for i in range(n):
    map_.append(list(map(int, input())))

def bfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    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 and nx < n and ny >= 0 and ny < m:
                if map_[nx][ny] == 1:
                    map_[nx][ny] = map_[x][y] + 1
                    queue.append((nx, ny))
    return map_[-1][-1]

print(bfs(0, 0))

---

설명

bfs로 풀었다.

처음 시작 좌표를 기준으로 상하좌우 각 4방향으로 이동이 가능한경우 숫자를 하나씩 늘려가며 돌렸다.

 

항상 계속 풀어보고 공부해야지 해야지 하면서 정작 하질 못하고 있다가 오랜만에 문제를 하나 풀어볼까 싶어서

좀 쉬운문제가 없을까 찾다가 풀어봤다.

역시나 오랜만이라 그런지 생각보다 시간이 조금 걸렸고 if로 조건을 걸때 부호를 반대로 넣어서 처음에 틀렸다.

 

다시 새로운 해를 맞이하면서 복습도 열심히 해야지...

 

---

DFS/BFS 설명

탐색 알고리즘 DFS/BFS