acmicpc.net 1697(BFS), 1963(BFS), 5014(BFS), 10026(BFS)

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

bfs문제.

# -*- encoding: cp949 -*-
import Queue

short = 99999999
def bfs(n,k):
    global short
    visited = [[0,0,0] for i in xrange(1000000)] #-, +, *2 의 방법으로 방문했었는지 체크
    q = Queue.Queue()
    q.put([n,0]) #첫번째위치와 거리 0으로 시작하므로 0.
    for i in xrange(3): #첫번째 위치는 다 방문했다고 초기화
        visited[n][i] = 1
    while not q.empty():
        p = q.get()
        if p[0]==k: #도착했을때 가장 짧은 경로로 세팅
            if short > p[1]:
                short = p[1]
        for i in xrange(3): #-, +, *2의 경우.
            tn = [p[0]-1,p[0]+1,2*p[0]][i]
            if k < n and i==0 and tn >=0: #5 0같이 입력값이 들어올경우 -만 넣으면 되므로 i==0일때로 가정했음.
                q.put([tn,p[1]+1])
                visited[tn][i] = 1
            if tn < 0 or tn > k+1 or tn > 999999: #나머지의 경우 예외처리
                continue
            if visited[tn][i]==0: #방문한 적이 없으면 방문
                q.put([tn,p[1]+1])
                visited[tn][i] = 1

n,k = map(int,raw_input().split())
bfs(n,k)
print short

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

bfs 문제..

# -*- encoding: cp949 -*-
import Queue

def bfs(a,b):
    global short
    visited = [0 for i in xrange(10000)] #해당 숫자를 방문했었는지 체크.
    q = Queue.Queue()
    q.put([a,0]) 
    visited[a] = 1
    while not q.empty():
        p = q.get()
        #print p
        if p[0]==b:
            if short > p[1]:
                short = p[1]
        for i in xrange(4): #4자리를 바꾸기 위한 반복문
            for j in xrange(10):
                if i==0:
                    tn = int(str(j)+str(p[0])[1:])
                elif i==1:
                    tn = int(str(p[0])[0] + str(j) + str(p[0])[2:])
                elif i==2:
                    tn = int(str(p[0])[:2] + str(j) + str(p[0])[3])
                else:
                    tn = int(str(p[0])[:3] + str(j))
                if tn < 1000 or tn > 9999 or prime[tn]!=0 or visited[tn]==1:
                    continue
                q.put([tn,p[1]+1])
                visited[tn] = 1

prime = [0 for i in xrange(10000)] #소수를 저장해놓을 리스트. 2부터 시작해서 인덱스 i의값이 1이면 소수이다. 에라토스테네스의 체를 이용.
for i in xrange(2,10000):
    for j in xrange(i,10000,i):
        if j==i:
            continue
        prime[j] = 1
#for i in xrange(2,10000): #소수 확인용
#    if prime[i]==0:
#        print i
for t in xrange(input()):
    a,b = map(int,raw_input().split())
    short = 99999999
    bfs(a,b)
    print short

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

쉬운 bfs. bfs는 문제 유형이 다 고만고만한것같다.

# -*- encoding: cp949 -*-
import Queue

short = 99999999
def bfs(f,s):
    global short
    visited = [0 for i in xrange(f+1)] 
    q = Queue.Queue()
    q.put([s,0])
    visited[s] = 1
    while not q.empty():
        p = q.get()
        if p[0]==g:
            if short > p[1]:
                short = p[1]
        for i in xrange(2):
            tn = p[0] + [u,-d][i]
            if tn < 0 or tn > f or visited[tn]==1:
                continue
            q.put([tn, p[1]+1])
            visited[tn] = 1

f,s,g,u,d = map(int,raw_input().split())
bfs(f,s)
print short if short != 99999999 else 'use the stairs'

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

쉽다.

# -*- encoding: cp949 -*-
import Queue
  
def bfs(y,x,color):
    global count
    global precinct
    visited = [[0 for j in xrange(len(precinct))] for i in xrange(len(precinct))] 
    q = Queue.Queue()
    q.put([y,x]) 
    while not q.empty():
        p = q.get()
        for i in xrange(4): 
            y,x = p[0]+[1,0,-1,0][i],p[1]+[0,-1,0,1][i]
            if y>len(precinct)-1 or x>len(precinct)-1 or x<0 or y<0:
                continue
            if visited[y][x]==0 and precinct[y][x]==color: 
                precinct[y][x] = count
                q.put([y,x])
                visited[y][x] = 1
 
rgb = [list(raw_input()) for i in xrange(input())]
for k in xrange(2):
    precinct = [[0 for i in xrange(len(rgb))] for j in xrange(len(rgb))]
    for i in xrange(len(rgb)):
        for j in xrange(len(rgb)):
            precinct[i][j] = rgb[i][j]
            if k==1 and precinct[i][j]=='G':
                precinct[i][j] = 'R'
 
    count = 0
    for i in xrange(len(precinct)):
        for j in xrange(len(precinct)):
            if type(precinct[i][j]) is not int:
                #print i,j
                count += 1
                bfs(i,j,precinct[i][j])
 
    #print '\n'.join(map(str,precinct))
    print count,