[BOJ-2178] 미로탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

---

[풀이]

 

전형적인 BFS 탐색 문제이다.

- 먼저 큐에 (시작점 y좌표:0, 시작점 x좌표: 0, 경로수: 시작카운트=1) 넣는다.

- 현위치 방문안했으면, 방문을 한다.

- 현위치의 상/하/좌/우 중 N행M열 배열원소이고, 아직 방문하지 않은 상태의 '1'(이동할 수 있는칸)

- 현위치의 cnt에 1을 더하여 큐에 추가한다.

 

(python)

# -*- coding: utf-8 -*-
# 2178. 미로찾기
import sys
from collections import deque

N,M=0,0
MAP=None
visited=None
q=deque()

dy=[-1,1,0,0] #상하좌우
dx=[0,0,-1,1]

def isRange(y,x):
    global N,M
    if(y>=0 and y<N) and (x>=0 and x<M):
        return True
    return False

def bfs():
    global N,M, visited, MAP
    while q:
        y,x,cnt=q.popleft()
        if(y==N-1 and x==M-1):
            return cnt
        if not visited[y][x]: #현위치에서 아직 방문하지 않았다면
            visited[y][x]=True
            
            for i in range(4):
                nexty=y+dy[i]
                nextx=x+dx[i]
                #적절한위치인지 확인
                if isRange(nexty, nextx):
                    #아직 방문을 안한 상태이고 1이라면
                    if (not visited[nexty][nextx]) and (MAP[nexty][nextx]=='1'):
                        q.append((nexty,nextx,cnt+1))

def main():
    global N,M, visited, MAP
    # N: 행, M: 열
    N,M= map(int , sys.stdin.readline().split())
    MAP=[list(sys.stdin.readline().strip()) for _ in range(N)]
    visited=[[False]*M for _ in range(N)]
    q.append((0,0,1))
    result= bfs()
    print(result)
    
if __name__=='__main__':
    main()

---

(python)

이전에 푼 코드이다.

클래스를 만들어서했는데 위의 코드보다 시간과 메모리수가 적었고 효율적이다.

# -*- coding: utf-8 -*-
import sys

class Maze:
    def __init__(self, N, M):
        self.N= N  #행
        self.M= M #열
        self.maze= [] #maze
        self.visited=[[False]*M for _ in range(N)] #방문리스트
        #우선순위
        # 아래, 오른쪽, 위, 왼쪽
        self.directions=[(1,0), (0,1), (-1,0), (0,-1)]
        
        self.q=[]
        
    def isRange(self, y,x):#현재위치가 N*M 배열의 원소에 적합한지 확인
        if (y<0) or (y>=self.N) or (x<0) or (x>=self.M):
            return False
        return True

    def bfs(self):
        while self.q:
            cury, curx, now_cnt =self.q.pop(0)# 현재위치, '1'개수 출력
            
            #현재위치가 방문하지 않은 상태라면..
            if self.visited[cury][curx] is False:
                self.visited[cury][curx]=True #방문을 한다
                
                #만일 현재위치가 (N-1, M-1)이라면
                if (cury==self.N-1) and (curx==self.M-1):
                    return now_cnt

                #현재위치의 오른쪽/아래/위/왼쪽 순으로 살펴본다
                for dy, dx in self.directions:
                    nexty= cury+dy
                    nextx= curx+dx
                    
                    #N*M 배열안의 원소인가?
                    if self.isRange(nexty, nextx):
                        # 다음 노드의 값이 '1'이고 아직 방문하지 않은 상태인가?
                        if (self.maze[nexty][nextx]=='1') and (self.visited[nexty][nextx] is False):
                            self.q.append((nexty, nextx, now_cnt+1)) #큐에 추가

def main():
    #행/열 구하기
    N,M = map(int, sys.stdin.readline().split())
    #maze객체 생성
    maze=Maze(N,M)
    
    #미로 지도 그리기
    for y in range(N):
        tmp=list(sys.stdin.readline().strip())
        maze.maze.append(tmp)

    #미로찾기 탐색(bfs)
    #시작점: (0,0) , 도착점: (N-1, M-1)
    #시작점 큐에 넣기
    maze.q.append((0,0,1))
    result=maze.bfs()
    print(result)
    
            
if __name__=='__main__':
    main()