BFS, DFS 스페샬 (백준 1012, 2178, 1389, 1697)

이전 게시글에서 BFS와 DFS에 대해 다뤘었다.

 

이번에는 그 응용.

첫번째는 1012번이다.

말이 어렵지 그냥 1 연속된 칸의 갯수를 구하는 문제다.

(x,y)의 값만 잘 설정한 뒤에는 dfs든 bfs든 상관없이 풀이해도 된다.

t=int(input())
for _ in range(t):
    stack=[]
    li=[]
    cnt=0
    x1=[1,-1,0,0]
    x2=[0,0,1,-1]
    m,n,k=map(int, input().split())
    space=[[0]*n for x in range(m)]
    check=[[0]*n for x in range(m)]
    for _ in range(k):
        a,b=map(int, input().split())
        space[a][b]=1
        li.append([a,b])
    for x in range(m):
        for y in range(n):
            if space[x][y]==1 and check[x][y]==0:
                cnt+=1
                check[x][y]=1
                stack.append([x,y])
                while stack:
                    a,b=stack.pop()
                    check[a][b]=1
                    for i in range(4):
                        A=a+x1[i]
                        B=b+x2[i]
                        if (0<=A<m) and (0<=B<n):
                            if space[A][B]==1 and check[A][B]==0:
                                stack.append([A,B])
    print(cnt)

다음은 2178번

정석적인 길찾기 문제이다.

def miro(space,vis):
    q=[(0,0)]
    vis[0][0]=1
    while q:
        x,y=q.pop(0)
        if x==n-1 and y==m-1:
            return vis[x][y]
        dx=[0,0,1,-1]
        dy=[1,-1,0,0]
        for i in range(4):
            ax=x+dx[i]
            ay=y+dy[i]
            if 0<=ax<n and 0<=ay<m and vis[ax][ay]==0 and space[ax][ay]==1:
                q.append((ax,ay))
                vis[ax][ay]=vis[x][y]+1
n,m=map(int,input().split())
space=[]
vis=[[0]*m for x in range(n)]
vis2=[[0]*m for x in range(n)]
res=[]
res2=[]
for x in range(n):
    inp=list(str(input()))
    inp=list(map(int,inp))
    space.append(inp)
print(miro(space,vis))

다음은 1389번, 몇명을 거쳐서 사람을 만날 수 있는가를 케빈베이컨 수라고 하는데 이 수가 가장 작은 사람을 구하는 문제다. A라는 사람부터 N명의 사람까지의 케빈 베이컨 수를 모두 더한 뒤에 리스트에 넣고, 비교하는 식으로 코드를 작성했다.

def bfs(v,vis):
    q1=[v]
    q2=[]
    c=[0 for x in range(102)]
    cnt=1
    vis.append(v)
    while q1:
        q2=[]
        while q1:
            v=q1.pop(0)
            for x in range(102):
                if li[x][v]==1 and x not in vis:
                    vis.append(x)
                    q2.append(x)
                    c[x]=cnt
        q1=q2[:]

        cnt+=1
    return c

n,m=map(int,input().split())
num=[]
res=[]
li=[[0]*(102) for x in range(102)]
LIST=[]
for x in range(m):
    a,b=map(int,input().split())
    li[a][b]=1
    li[b][a]=1
    LIST.append(a)
    LIST.append(b)
LIST=list(set(LIST))
LIST.sort()
for x in LIST:
    vis=[]
    num.append(sum(bfs(x,vis)))
MIN=99999
for x in range(len(num)):
    if MIN>num[x]:
        MIN=num[x]
        res=x
print(LIST[res])

마지막 1697번. 처음 봤을때, bfs인 것을 떠올리기가 쉽지 않아서 실버 1인 것 같다. 

from collections import deque

def bfs(arr, n, k):
    q = deque()
    q.append(n)
    while q:
        i=q.popleft()
        if i==k:
            return arr[i]
        for j in (i+1, i-1, 2*i):
            if (0 <= j < 100001) and arr[j] == 0:
                arr[j] = arr[i] + 1
                q.append(j)

n,k= map(int, input().split())
li = [0] * 100001
print(bfs(li, n, k))