S1 2178. 미로 탐색

문제 보기 :  2178번: 미로 탐색 (acmicpc.net)

---

문제

• 정답률 : 44%

---

작성 코드 & 풀이 과정 코멘트

1) 1차 풀이

from collections import deque

def bfs(g,start,n,m):
    d = [(0,-1),(0,1),(-1,0),(1,0)]
    vis = [[False]*m for i in range(n)]
    vis[start[0]][start[1]]=True

    dd = deque([start])
    while dd:
        x,y = dd.popleft()
        if x == n-1 and y == m-1:
            return g[x][y]

        for dx,dy in d:
            X = dx+x ; Y = dy+y
            if 0<=X<n and 0<=Y<m and g[X][Y]==1 and not vis[X][Y]:
                vis[X][Y] = True
                g[X][Y] = g[x][y]+1
                dd.append((X,Y))

n,m = map(int,input().split())
g = [list(map(int,list(input()))) for i in range(n)]
print(bfs(g,(0,0),n,m))

이것도 정답이다.

 

2) 2차 풀이

from collections import deque

def miro(graph, start):
    answer = 1
    
    direction = [(-1,0),(1,0),(0,1),(0,-1)]
    visited = [[False]*m for _ in range(n)]

    visited[start[0]][start[1]] = True #현재 위치

    dd = deque([start])
    while dd:
        x,y = dd.popleft()
        if x == n-1 and y == m-1:
            return graph[x][y]
        for dx,dy in direction:
            xx = x+dx ; yy = y+dy
            if 0<=xx<n and 0<=yy<m and graph[xx][yy]==1 and not visited[xx][yy]:
                visited[xx][yy] = True
                graph[xx][yy] = graph[x][y] + 1#0
                answer += 1
                dd.append((xx,yy))
    return answer

n,m = map(int,input().split())
graph = [list(map(int,list(input()))) for _ in range(n)]
print(miro(graph,(0,0)))

2차 풀이는 이렇게 변경했다. 근데 다시 보니, answer를 없애고 return graph[-1][-1]으로 변경해도 될 것 같다.

Input >
4 6
101111
101010
101011
111011

Output > 15

예제를 위와 같이 입력하면 graph는
[[1, 0, 9, 10, 11, 12],
[2, 0, 8, 0, 12, 0],
[3, 0, 7, 0, 13, 14],
[4, 5, 6, 0, 14, 15]]
이렇게 만들어진다.
그럼 정답은 마지막 부분인 15다!