acmicpc.net 1260(DFS, BFS), 2178(BFS)

dfs : 끝까지 들어간후 다음걸로 넘어감. 스택으로 구현 가능(또는 재귀나 리스트 등등으로 구현 가능)

bfs : 얇게 다 퍼진 후 그다음에 들어감. 큐로 구현 가능.

acmicpc 1260번 문제를 대상으로 설명.

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

도움 많이 됬던 블로그 : http://hyulim.tistory.com/345 + 책

# -*- encoding: cp949 -*-
import Queue
def dfs(graph,v):
    global visited
    global answer
    stack = []
    stack.append(v)
    while stack!=[]:
        j = stack.pop()
        if visited[j]==0:
            visited[j] = 1
            answer += str(j)+' '
        for i in range(len(graph)-1,-1,-1):
            if graph[j][i]==1 and visited[i]==0:
                stack.append(i)

def bfs(path, v):
    global visited
    global answer
    q = Queue.Queue()
    q.put(v)
    while not q.empty():
        j = q.get()
        if visited[j]==0:
            answer += str(j)+' '
            visited[j] = 1
        for i in range(len(graph)):
            if graph[j][i]==1 and visited[i]==0:
                q.put(i)

n,m,v = map(int,raw_input().split())
graph = [[0 for j in range(n+1)] for i in range(n+1)]

for i in range(int(m)):
    x,y = map(int,raw_input().split())
    graph[x][y] = 1 #양방향 간선이므로 아래처럼 y,x위치에도 표시를 해준다.
    graph[y][x] = 1

answer = ''
visited = [0 for i in range(n+1)]  
dfs(graph,v)
print answer

answer = ''
visited = [0 for i in range(n+1)]  
bfs(graph,v)
print answer

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

bfs문제.

# -*- encoding: cp949 -*-
import Queue
n,m = map(int,raw_input().split())
maps = [map(int,raw_input()) for i in range(n)]
visited = [[0 for j in range(m)] for i in range(n)]
move = 0
q = Queue.Queue()
q.put([0,0])
visited[0][0] = 1
while not q.empty():
    for k in range(q.qsize()):
        p = q.get()
        #print p,n,m
        if p[0]==n-1 and p[1]==m-1:
            print move+1
            exit(1)
        for i in range(4):
            y,x = p[0]+[1,0,-1,0][i],p[1]+[0,-1,0,1][i]
            #print 'xy =',x,y
            if y>n-1 or x>m-1 or x<0 or y<0:
                continue
            if visited[y][x]==0 and maps[y][x]==1:
                #print 'xy =',[y,x],visited[y][x],maps[y][x]
                q.put([y,x])
                visited[y][x] = 1
    move += 1