acmicpc.net 13565(BFS,DFS), 1261(다익스트라)

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

DFS나 BFS로 풀면 된다. 검색해서 가장 먼저 보이는 소스가 BFS여서 BFS로품

def bfs(y,x):
    visited = [[0 for j in xrange(n)] for i in xrange(m)] 
    q = Queue.Queue()
    q.put([y,x]) 
    visited[y][x] = 1
    while not q.empty():
        p = q.get()
        if p[0]==m-1:
            return True
        for i in xrange(3): 
            ty,tx = p[0]+[1,0,0,-1][i],p[1]+[0,-1,1,0][i]
            if ty<0 or tx<0 or ty>m-1 or tx>n-1:
                continue
            if visited[ty][tx]==0 and arr[ty][tx]==0:
                q.put([ty,tx])
                visited[ty][tx] = 1
    return False

m,n=map(int,raw_input().split())
arr = [map(int,raw_input()) for i in xrange(m)]
flag = True
for i in xrange(n):
    if arr[0][i]==0 and bfs(0,i):
        print 'YES'
        flag = False
        break
if flag:
    print 'NO'

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

다익스트라로 모델링해서 푼다. 현재 위치에서 갈수 있는 방향을 조사해서 벽이 1이면 거기까지 가는

비용을 1이라고 두고 풀면 된다.

# -*- encoding: cp949 -*-
import Queue
def dijkstra(src):
    dist = [999999 for i in xrange(m*n+1)]
    dist[src] = 0 
    q = Queue.Queue()
    q.put([src,0]) 
    while not q.empty():
        here,cost = q.get()
        if dist[here] < cost:
            continue
        for i in xrange(len(adj[here])):
            there = adj[here][i][0]
            nextdist = cost + adj[here][i][1]
            if dist[there] > nextdist:
                dist[there] = nextdist
                q.put([there,nextdist])
  
    return dist[1:]

m,n = map(int,raw_input().split())
adj = [[] for i in xrange(m*n+1)]
go = [map(int,raw_input()) for i in xrange(n)]
for i in xrange(n):
    for j in xrange(m):
        for k in xrange(4):
            y,x = i+[1,0,0,-1][k],j+[0,-1,1,0][k]
            if y<0 or x<0 or y>n-1 or x>m-1:
                continue
            
            adj[i*m + j + 1].append([y*m + x + 1,go[y][x]])
d = dijkstra(1)
print d[m*n-1]