둔필승총

탐색Search이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 대표적인 탐색 알고리즘이 DFS와 BFS이다. 프로그래밍에서는 자료구조 안에서 탐색을 하는데 DFS와 BFS를 알려면 스택과 큐에 관한 자료구조를 알아야된다.

스택

스택Stack은 레고 쌓기에 비유할 수 있다. 레고는 아래에서부터 위로 차곡차곡 쌓는다. 맨 아래에 레고를 빼기 위해서는 위에 레고를 빼야 된다. 즉, 먼저 쌓은 것이 제일 나중에 뺄 수 있다. 선입후출(First In Last Out) 또는 후입선출(Last In First Out) 구조 라고 한다. 

stack=[]
#삽입(1) - 삭제() - 삽입(3) - 삽입(5) - 삽입(6) - 삭제() - 삽입(2) - 삭제()
stack.append(1)
stack.pop()
stack.append(3)
stack.append(5)
stack.append(6)
stack.pop()
stack.append(2)
stack.pop()
print(stack)#[3,5]
print(stack[::-1])#[5,3]

append() 메서드는 리스트의 가장 뒤쪽에 데이터를 삽입하고, pop() 메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼낸다.

큐

큐Queue는 대기 줄에 비유할 수 있다. 우리가 놀이공원에 입장하기 위해 줄을 설 때, 먼저 온 사람이 먼저 들어가게 된다. 나중에 온 사람이 나중에 들어가기 때문에 흔히 '공정한' 자료구조라고 비유된다. 이러한 구조를 선입선출(First In First Out)라고 한다.

from collections import deque
queue=deque()
#삽입(4) - 삽입(2) - 삽입(1) - 삽입(8) - 삭제() - 삭제() - 삽입(4)
queue.append(4)
queue.append(2)
queue.append(1)
queue.append(8)
queue.popleft()
queue.popleft()
queue.append(4)

print(queue)
queue.revers()
print(queue)

파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용한다. deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다.

deque객체를 자료형으로 변경하고자 한다면 list(queue)를 사용하면 리스트 자료형이 반환된다.

DFS

DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 알려면 그래프의 표현 방식을 알아야 된다. 

그래프는 2가지 방식으로 표현할 수 있는데 인접 행렬 방식과 인접 리스트 방식이 있다.

인접 행렬 방식은 2차원 배열로 그래프의 연결 관계를 표현하는 방식이고 인접 리스트 방식은 리스트로 그래프의 연결 관계를 표현하는 방식이다. 

인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 연결이 되어 있지 않은 노드끼리는 무한Infinity의 비용이라고 작성한다. 

인접 행렬 방식 예제

INF = 9999999999

graph = [
    [0,7,5],
    [7,0,INF],
    [5,INF,0]
]

print(graph)

[[0,7,5],[7,0,99999999],[5,999999999,0]]

 인접 리스트 방식에서는 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다. C++이나 Java와 같은 프로그래밍 언어에서는 별도로 연결 리스트 기능을 위한 표준 라이브러리를 제공한다.

 반면에 파이썬은 기본 자료형인 리스트 자료형이 append()와 메소드를 제공하므로, 전통적인 프로그래밍 언어에서의 배열과 연결 리스트의 기능을 모두 기본으로 제공한다. 파이썬으로 인접 리스트를 이용해 그래프를 표현하고자 할 때에도 단순히 2차원 리스트를 이용하면 된다. 

# 행(ROW)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

#노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))

#노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0,7))

#노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0,5))

print(graph)

DFS는 어떻게 작동할까? DFS는 깊이 우선 탐색 알고리즘이다. 이 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

방문 처리는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.

깊이 우선 탐색 알고리즘인 DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다는 특징이 있다. 

또한 DFS는 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다. 

def dfs(graph, v, visited):
    #현재 노드를 방문 처리
    visited[v]=True
    print(v,end=" ")
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)


#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph= [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

#각 노드가 방문된 정보를 리스트 자료형으로 표현
visited = [False]*9

#정의된 DFS 함수 호출
dfs(graph,1,visited)

#1 2 7 6 8 3 4 5

BFS

BFS(Breadth First Search) 알고리즘은 '너비 우선 탐색'이라는 의미를 가진다. BFS는 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다고 했는데, BFS는 그 반대로 가까이 있는것부터 차근차근 탐색해나간다. 

BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용한다. 인접한 노드를 반복적으로 큐에 넣어서 가까운 노드부터 탐색해서 탐색할 수 있을때까지 찾아나가는 것이다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

BFS는 큐 자료구조에 기초한다. 구현함에 있어 deque라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어 O(N)의 시간이 소요된다. 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이다.

from collections import deque

graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5]
]
visited=[False]*9

def bfs(graph,start,visited):
    queue=deque([start])
    visited[start]=True
    while queue:
        #큐에서 하나의 원소를 뽑아 출력
        v=queue.popleft()
        print(v,end=' ')
        #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True

2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각하면 풀이 방법을 조금 더 쉽게 떠올릴 수 있다.

www.acmicpc.net/problem/1012

[문제 풀이]

문제가 길지만 정리하자면 배추밭에서 1이 있는곳은 배추가 있는곳, 0은 배추가 없는 곳이다. 1이 있는 곳을 DFS해서 주위에 0으로 둘러쌓일때까지 구하고, 그 갯수를 파악해서 출력하면 된다. 혹은 BFS를 통해서 풀 수 있다. (복습을 할 때 BFS를 통해서 풀었다.)

1. 첫번째 풀이법

import sys
sys.setrecursionlimit(10000)
def dfs(x,y):
    if x<=-1 or x>=n or y<=-1 or y>=n:
        return False
    if graph[x][y]==1:
        graph[x][y]=0
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True
    return False
t = int(input())
for _ in range(t):
    m,n,k=map(int,input().split())
    graph=[[0]*(m) for _ in range(n)]
    result=0
    for _ in range(k):
        x,y=map(int,input().split())
        graph[y][x]=1
    for i in range(n):
        for j in range(m):
            if dfs(i,j):
                result+=1
    print(result)

dfs 함수를 정의해 주면서 먼저 x와 y좌표가 범위를 벗어날때는 False를 반환하게 두었다. 그러나 이렇게 하면 만약 x,y 에 (0,0) 이 들어갔을 경우 index error가 일어나게 된다. 

2. 두번째 풀이법

import sys
sys.setrecursionlimit(10000)
def dfs(x,y):
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    for i in range(4):
        nx,ny = x+dx[i],y+dy[i]
        if nx>=n or nx<0 or ny>=m or ny<0:
            continue
        if graph[nx][ny]==1:
            graph[nx][ny]=0
            dfs(nx,ny)
t = int(input())
for _ in range(t):
    m,n,k=map(int,input().split())
    graph=[[0]*(m) for _ in range(n)]
    result=0
    for _ in range(k):
        x,y=map(int,input().split())
        graph[y][x]=1
    for i in range(n):
        for j in range(m):
            if dfs(i,j):
                result+=1
    print(result)

두 번째 풀이법은 dx, dy를 통해서 상하좌우를 탐색하기 때문에 상관없지만 첫번째 풀이법은 의도치 않은 인덱스에 접근할 수 있기때문에 오류가 난다.

3. 세번째 풀이 (BFS를 통해서 해결)

BFS를 통해서 푸는 것으로 익숙해질려고 했다.(DFS를 사용하니까 계속 recursion error 같은 것들을 신경써야해서..) 먼저 BFS는 deque를 사용하므로 상단에 deque를 import 시켜준다.

from collections import deque

bfs는 파라미터로 a,b를 받는다. 여기서 a, b는 배추밭에서 1인 것, 즉 배추가 있는곳을 찾으면 bfs를 실행해서 주위가 0으로 둘러쌓인것에 닿을때까지 실행해준다. 그리고 bfs함수가 끝나면 total_num(우리가 출력해야 되는 값)을 하나 더해준다.

 매번 헷갈리지만 주의해야 할 것은 2차원 배열에 x,y축의 값이다.. 가로가 m이지만 배열의 첫번째는 y축의 값이 들어가는.. 이런것을 계속 생각해주어야 한다. 

from collections import deque
def bfs(a,b):
    q=deque([])
    q.append((a,b))
    graph[a][b]=0
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    bechu = 0
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx>=0 and nx<n and ny>=0 and ny<m and graph[nx][ny]==1:
                q.append((nx,ny))
                graph[nx][ny]=0
t = int(input())
for _ in range(t):
    m,n,k = map(int,input().split())
    graph=[[0]*(m) for _ in range(n)]
    total_num = 0
    for i in range(k):
        x,y = map(int,input().split())
        graph[y][x]=1
    for i in range(n):
        for j in range(m):
            if graph[i][j]==1:
                bfs(i,j)
                total_num+=1
    print(total_num)

www.acmicpc.net/problem/11724

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1

2

예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2

1

[문제 해설]

먼저 문제를 해결하려면 연결 요소라는 개념을 알아야 한다. 연결요소란 그래프의 개수와 같다. 정점 사이에 겹쳐진게 없고, 나누어진 각각의 그래프를 연결 요소라고 생각하면 된다. 연결 요소를 구하는 것은 DFS나 BFS 탐색을 이용해서 할 수 있다.

정점의 개수 n과 간선의 개수 m을 먼저 입력 받는다. 그리고 graph라는 2차원 배열을 만들어서 연결된 정보를 얻는다. visited 배열은 각각의 정점에 방문했는지 확인하는것으로 False로 초기화시켜놓는다. 

dfs함수를 만들면 되는데 파라미터로는 v, 즉 노드를 받는다. visited[v]를 True로 대입하고 v와 연결된 곳 중 방문하지 않은 곳을 dfs해준다. 이렇게 dfs를 다 하면 result값을 1 추가한다. 출력값은 result를 출력하면 되는것이다.

import sys
sys.setrecursionlimit(10000)

n,m = map(int,input().split())
graph=[[] for _ in range(n+1)]
visited=[False]*(n+1)
result=0
for _ in range(m):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(v):
    visited[v]=True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)
for i in range(1,n+1):
    if not visited[i]:
        dfs(i)
        result+=1
print(result)

##의문점##

이 문제를 제출하니까 pypy3으로는 해결되는데 python3으로는 시간초과가 난다. 그래서 질문을 올렸더니...

www.acmicpc.net/board/view/66897#comment-111276

파이썬 루프쪽 구현을 잘못해서 pypy구현체가 훨 빠르다고... 

(나중에 확인해봐야겠다)

www.acmicpc.net/problem/2606

문제

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

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

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

입력

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

출력

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

예제 입력 1

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1

4

[문제 해설]

문제 이해는 아주 잘 되는 편이였다. 1번이 바이러스에 걸리면 1번과 연결된 모든 컴퓨터가 바이러스에 걸린다. 1번에 의해서 몇개의 컴퓨터가 바이러스에 걸리는지 확인하면 되는 문제이다.

먼저 1부터 해서 깊게 파고들어서 연결된 컴퓨터를 모두 확인해야 되기 때문에 DFS를 떠올릴 수 있다. DFS를 통해서 풀었다.

(밑에 코드는 정답은 아니고 시행착오 중 하나)

n = int(input())
m= int(input())
computer=[]
visited=[False]*(n+1)

for i in range(m):
    computer.append(list(map(int,input().split())))

def dfs(computer,v,visited):
    visited[v]=True
    for i in range(m):
        x=computer[i][0]
        y=computer[i][1]
        if not visited[y] and x==v:
            dfs(computer,y,visited)
            print(visited)
dfs(computer,1,visited)
answer=0
for i in range(1,n+1):
    if visited[i]:
        answer+=1
print(answer-1)

위에 코드는 처음에 짠 코드이다. 연결된 간선 모두를 반복문을 통해 확인하고 방문되지 않은곳을 다 방문하여 확인하였다. 예제 입력에 있는 숫자들을 복사하면 출력 값이 잘 나온다.

 그러나 제출하면 계속 '틀렸습니다' 가 되어서 코드를 계속해서 보았다.

 예제 입력을 조금만 틀어서 입력하니까 문제를 찾을 수 있었다.

7
6
1 2
2 3
5 1#여기만 바꿈
5 2
5 6
4 7

사실 연결된 것은 똑같기 때문에 같은 값이 나와야 되는데 출력값은 4가 아니였다. 

양쪽에 연결된 것을 확인하지 않았기 때문이었다.

양쪽에 연결하는 코드를 추가해주면 된다.

n = int(input())
m= int(input())
computer=[]
visited=[False]*(n+1)

for i in range(m):
    computer.append(list(map(int,input().split())))

def dfs(computer,v,visited):
    visited[v]=True
    for i in range(m):
        x=computer[i][0]
        y=computer[i][1]
        if not visited[y] and x==v:
            dfs(computer,y,visited)
        if not visited[x] and y==v:
            dfs(computer,x,visited)
dfs(computer,1,visited)
answer=0
for i in range(1,n+1):
    if visited[i]:
        answer+=1
print(answer-1)

www.acmicpc.net/problem/2667

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 1

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 1

3
7
8
9

[문제 풀이]

일단 <그림1>에서 1이 적힌 곳을 찾아서 0이 나올때까지 끝까지 탐색을 시켜줘야된다. 여기서 깊이 우선 탐색을 생각해 낼 수 있다. 지도에서 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다. 

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.

2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.

n = int(input())
graph=[]#지도
apt=[]
for _ in range(n):
    graph.append(list(map(int,input())))

def dfs(x,y):
    global cnt
    if x<=-1 or x>=n or y<=-1 or y>=n:
        return False
    if graph[x][y]==1:
        graph[x][y]=0
        cnt+=1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True
    return False
cnt=0
for i in range(n):
    for j in range(n):
        if dfs(i,j)==True:
            apt.append(cnt)
            cnt =0
apt.sort()
print(len(apt))
for i in range(len(apt)):
    print(apt[i])

코드를 설명해보겠다.

일단 출력해야 되는 것은 2개이다. 아파트 단지의 개수와 단지 안에 아파트 수이다. apt 리스트에는 아파트 수가 담겨있게 하고 단지 수는 len(apt)로 구할 생각을 했다.

위에서 말했듯이 dfs로 풀었다. 일단 dfs함수에서 x,y 가 갈 수 없는 곳을 갔을 때는 False를 return해 주었다.

그리고 graph에서 값이 1일때 단지 수를 세면 되니까 1일때 graph의 값을 방문했다는 의미로 0을 대입해주고 아파트 수 즉 cnt를 1씩 늘여간다. 

그리고 dfs함수로 상, 하, 좌, 우를 방문한다.

n*n 반복문으로 apt를 구한다.