IT-garden

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

그래프 알고리즘

그래프 이론

정답

import sys
from collections import deque

input = lambda : sys.stdin.readline().strip()

dx = [-1, -1, 0, 1, 1, 1, 0, -1] # 위부터 시계방향
dy = [0, 1, 1, 1, 0, -1, -1, -1]

def bfs(c):
    de=deque()
    de.append(c)

    while len(de) != 0:
        c=de.popleft()

        for i in range(8):
            nx = c[0] + dx[i]
            ny = c[1] + dy[i]

            if 0 <= nx < h and 0 <= ny < w:
                if a[nx][ny] == 1:
                    a[nx][ny] = 0
                    de.append([nx,ny])

while True:
    w, h=map(int, input().split())

    if w == 0 and h == 0:
        break

    a=[list(map(int,input().split())) for i in range(h)]
    c=0
    
    for i in range(h):
        for j in range(w):
            if a[i][j] == 1:
                c += 1
                bfs([i,j])
                
    print(c)

백준 알고리즘 4963번 : www.acmicpc.net/problem/4963

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력과 출력

알고리즘 분류

BFS

정답

import sys
from collections import deque

input= lambda : sys.stdin.readline().strip()

n,m=map(int,input().split())

a = [list(map(int, input())) for i in range(n)]

ch=[[0]*m for i in range(n)]
dx = [-1, 0, 1, 0] #위,오른쪽,아래,왼쪽 
dy = [0, 1, 0, -1]

de=deque()
de.append([0,0])
ch[0][0]=1

while len(de) != 0:
    x, y = de.popleft()
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if a[nx][ny] != 0 and ch[nx][ny] == 0:    
                ch[nx][ny] = ch[x][y] + 1
                de.append([nx, ny])

print(ch[n-1][m-1])

백준 알고리즘 2178번 : www.acmicpc.net/problem/2178

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력과 출력

알고리즘 분류

플로이드 와샬 알고리즘 

정답

from collections import deque

a=int(input())
b=int(input())

n=[list(map(int,input().split())) for i in range(b)]
m=[[] for i in range(a+1)]

ch=[0]*(a+1)

for i in range(b):
    x, y= n[i]
    m[x].append(y)
    m[y].append(x)

s=1 #시작점

def bfs(s):
    c=0 
    de=deque()
    de.append(s)
    ch[s]=1

    while len(de) != 0:
        d=de.popleft() 
        c += 1

        for i in m[d]:
            if ch[i] != 1:
                ch[i]=1
                de.append(i)
        
    print(c-1)
    
bfs(s)

백준 알고리즘 2606번 : www.acmicpc.net/problem/2606

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력과 출력

알고리즘 분류

BFS

DFS

정답

from collections import deque

n,m,v=map(int,input().split())

a=[[] for i in range(n+1)]

for i in range(m):
    x, y=map(int,input().split())
    a[x].append(y)
    a[y].append(x)

for i in a:
    i.sort()

def dfs(node):
    ch[node]=1
    print(node, end=' ')

    for i in a[node]:
        if ch[i] != 1:
            dfs(i)

ch=[0]*(n+1)
dfs(v)

print()

def bfs(start):
    de=deque()
    de.append(start)
    che[start]=1

    while len(de) != 0:
        now=de.popleft()
        print(now, end=' ')
        
        for i in a[now]:
            if che[i] != 1:
                che[i]=1
                de.append(i)
    
che=[0]*(n+1)
bfs(v)

queue를 사용하면 런타임 에러가 나서 deque를 사용했습니다.

queue가 많이 느려서 그렇다고 하는데 정확하지는 않습니다.

백준 알고리즘 1260번 : www.acmicpc.net/problem/1260

너비 우선 탐색(BFS : Breadth First Search)은 시작점으로부터 가까운 점을 먼저 방문하고 멀리 떨어져 있는 점을 나중에 방문하는 탐색 방법입니다.

특징은 시작점으로부터 거리가 가까운 점의 순서로 탐색이 진행됩니다.

거리의 의미는 시작점으로부터 어느 점까지의 경로 중 가장 짧은 경로의 길이를 의미합니다.

즉, 거리가 a인 점들을 모두 방문하고 거리가 a + 1인 점들을 모두 방문합니다.

너비 우선 탐색은 크게 2가지 문제에서 자주 사용됩니다.

1. 그래프를 모두 탐색하는 문제

2. 특정 그래프에서 가중치가 모두 같을 때 최단거리를 찾는 문제

너비 우선 탐색의 방법은

1. 큐에서 하나를 꺼내 제거하고(제거 하는 것이 방문한 점)

2. 해당 점과 연결되어 있는 점들 중 방문하지 않은 점을 모두 큐에 넣습니다.

너비 우선 탐색에서는 큐를 사용합니다.

큐는 방문한 점들을 저장하고 제거하는데 사용하고 큐가 공백이 될 때까지 탐색이 계속됩니다.

위와 같은 그래프가 있다고 가정하고 너비 우선 탐색을 실시해보겠습니다.

시작점은 1로 생각하고 모든 그래프를 탐색하려고 합니다.

점을 방문할때는 더 작은 순서로 방문하도록 하겠습니다.

기존 그래프에서 1을 큐에 넣어줍니다. 1이 시작점이기 때문입니다.

그리고 1을 방문하여 큐에서 1을 제거하고 1과 연결되어 있는 점들 중 방문하지 않은 점인 2와 3을 큐에 넣습니다.

큐에서 다음으로 2를 방문하여 큐에서 2를 제거하고 2와 연결되어 있는 점들 중 방문하지 않은 점을 모두 큐에 넣습니다.

여기서 1은 이미 방문했기 때문에 큐에 넣지 않고 4와 5를 넣습니다.

다음으로 3를 방문하여 큐에서 3를 제거하고 3와 연결되어 있는 점들 중 방문하지 않은 점을 모두 큐에 넣습니다.

여기서 1은 이미 방문했기 때문에 6만 큐에 넣습니다.

큐에서 4를 방문하며 4를 제거합니다. 이때 4에 연결된 점들 중 방문하지 않은 점이 없기 때문에 큐에 값을 넣어주지 않습니다.

마찬가지로 5도 방문하고 큐에서 제거해줍니다.

마지막으로 6도 방문하고 큐에서 제거해줍니다.

그럼 모든 점들의 방문이 끝나 탐색이 종료됩니다.

위의 그래프에서 너비 우선 탐색의 방문 순서는 1 → 2 → 3 → 4 → 5→ 6 입니다.

큐를 이용한 너비 우선 탐색의 파이썬 코드입니다.

import queue

n = 6 # 정점의 수 : 6 (1, 2, 3, 4, 5, 6)
v = 1 # 시작점
b = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6]]

a = [[] for i in range(n+1)]

for i in range(len(b)):
    x, y = b[i]
    a[x].append(y)
    a[y].append(x)
    
for i in a: # 작은 수부터의 방문을 위해 정렬
    i.sort()

ch = [0] * (n+1)

def bfs(start):
    q = queue.Queue()
    q.put(start)
    ch[start] = 1

    while not q.empty():
        now = q.get()
        print(now, end=' ')
        for i in a[now]:
            if ch[i] != 1:
                ch[i] = 1
                q.put(i)
                
bfs(v)

# 최종 출력>>1 2 3 4 5 6

덱을 이용한 너비 우선 탐색의 파이썬 코드입니다.

from collections import deque

n = 6 #정점의 수 : 6 (1, 2, 3, 4, 5, 6)
v = 1 #시작점
b = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6]]

a=[[] for i in range(n+1)]

for i in range(len(b)):
    x, y = b[i]
    a[x].append(y)
    a[y].append(x)
    
for i in a: # 작은 수부터의 방문을 위해 정렬
    i.sort()

ch = [0] * (n+1)

def bfs(start):
    de = deque()
    de.append(start)
    ch[start] = 1 

    while len(de) != 0:
        now = de.popleft()
        print(now, end=' ')
        for i in a[now]:
            if ch[i] != 1:
                ch[i] = 1
                de.append(i)
                
bfs(v)

# 최종 출력>>1 2 3 4 5 6