5/9-10 스터디 문제

1번 문제.
https://www.acmicpc.net/problem/2178
-> 미로탐색

1번 문제 풀이 코드(BFS 이용)

import sys
from collections import deque

def bfs(x, y):
    deq = deque()
    deq.append((x, y))
    
    # 상좌하우 방향 설정
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]

    while deq:
        x, y = deq.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 matrix[nx][ny] == 0:
                continue

            if matrix[nx][ny] == 1:
                matrix[nx][ny] = matrix[x][y] + 1
                deq.append((nx, ny))
                
    # 최단거리
    return matrix[n-1][m-1]

# 테스트 케이스
n, m = map(int, sys.stdin.readline().rstrip().split())
# n개의 줄에 m개의 정수들 입력
matrix = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]

print(bfs(0, 0))    

=======================================================

DFS를 이용해서 풀려고 하다가 시간만 잡아먹었다....
본 문제는 최단거리를 구해야 하는 문제로서 BFS를 이용해서 푸는것이 효율적이다.

참고

https://loosie.tistory.com/151
http://blog.slarea.com/algorithm/techniques/dfs-bfs