수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력 1
5 17
예제 출력
4
힌트
수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.
[문제 해설]
처음 생각했던 것은 다이나믹 프로그래밍이였다. 각각의 위치에 가는 시간을 배열에 저장해서 다이나믹 프로그래밍으로 풀려고 했으나 생각보다 어려웠던 것은 뒤로 가는 경우와 앞으로 가는 경우까지 생각해야되서 복잡했다.
돌고 돌아 BFS로 풀게 되었다. 모든 장소를 0으로 초기화 시킨 배열 d도 준비한다. 출발점을 큐의 첫번째 원소로 먼저 넣는다. 그 점에서 -1, +1, *2 한 곳을 next로 두고 for문을 통해서 반복한다. next가 범위 안에 있고, d배열에서 방문하지 않은 0이면 d[next]는 d[v]+1값이 들어가고 next를 큐에 추가해준다. 그럼 n에서 k로 가는 최소점이 d배열에 들어가게 된다. 종료 조건은 큐에 k값이 들어간게 확인되었을때 d[v]를 출력해주고 종료하면 된다.
(나는 d배열에 어떤값이 들어가있는지 계속 헷갈려서 print로 찍어주었다. 주석은 무시하고 보면 된다_
from collections import deque
n, k = map(int, input().split())
# n에서 k로 가기
d=[0]*100001
def bfs(n):
queue=deque()
queue.append(n)
while queue:
v=queue.popleft()
if v==k:
print(d[v])
return
for next in (v-1,v+1,v*2):
if 0<=next<100001 and not d[next]:
# for i in range(20):
# print(d[i], end=' ')
# print()
d[next]=d[v]+1
queue.append(next)
bfs(n)
탐색Search이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 대표적인 탐색 알고리즘이 DFS와 BFS이다. 프로그래밍에서는 자료구조 안에서 탐색을 하는데 DFS와 BFS를 알려면 스택과 큐에 관한 자료구조를 알아야된다.
스택
스택Stack은 레고 쌓기에 비유할 수 있다. 레고는 아래에서부터 위로 차곡차곡 쌓는다. 맨 아래에 레고를 빼기 위해서는 위에 레고를 빼야 된다. 즉, 먼저 쌓은 것이 제일 나중에 뺄 수 있다. 선입후출(First In Last Out) 또는 후입선출(Last In First Out) 구조 라고 한다.
append() 메서드는 리스트의 가장 뒤쪽에 데이터를 삽입하고, pop() 메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼낸다.
큐
큐Queue는 대기 줄에 비유할 수 있다. 우리가 놀이공원에 입장하기 위해 줄을 설 때, 먼저 온 사람이 먼저 들어가게 된다. 나중에 온 사람이 나중에 들어가기 때문에 흔히 '공정한' 자료구조라고 비유된다. 이러한 구조를 선입선출(First In First Out)라고 한다.
인접 리스트 방식에서는 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다. 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차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각하면 풀이 방법을 조금 더 쉽게 떠올릴 수 있다.
이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬을 이용해서 이진탐색도 가능해지는 것이다.
선택 정렬(Selection Sort)
: 가장 먼저 생각이 날 수 있는 자연스러운 정렬 알고리즘
각 위치에 어떤 값이 들어갈지 찾는다.
가장 작은 값을 찾아서 0번 인덱스에 놓고, 두 번째로 작은 값을 찾아서 1번 인덱스에 놓고, 세 번째로 작은 값을 찾아서 2번 인덱스에 놓고.....
즉, 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 앞에서 2번째 데이터와 바꾸는 과정을 반복하자.
array = [2,4,5,1,3,9,7,8]
for i in range(len(array)):
min_index=i
for j in range(i+1,len(array)):
if array[min_index]>array[j]:
min_index=j
array[i],array[min_index]=array[min_index],array[i]
print(array)
선택 정렬의 시간 복잡도는 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 연산 횟수는 N+(N-1)+(N-2) ... 이렇기 때문에 O(N^2)시간복잡도가 나온다.
삽입 정렬(Insertion Sort)
: 각 값이 어떤 위치에 들어갈지 찾는다
정렬 문제의 경우 "절대적인 좋은 답"이란 없다. 상황에 따른 각 알고리즘의 장단점을 파악해야 올바른 알고리즘을 선택할 수 있다.
삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉽다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다.
삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다.
array = [7,5,9,0,3,1,2,8,6]
for i in range(1,len(array)):
for j in range(i,0,-1):#인덱스 i부터 1까지 감소하며 반복하는 문법
if array[j]<array[j-1]:
array[j],array[j-1]=array[j-1],array[j]
else:
break
print(array)
삽입 정렬의 시간복잡도는 O(N^2)이다. 그러나 최선의 경우 O(N)의 시간 복잡도를 가진다. 모두 정렬되어있으면 O(N)의 시간복잡도를 가진다.
합병 정렬(Merge Sort)
Divide and Conquer에서 대표적으로 설명하는 정렬 방식이다.
Divide에서는 리스트를 왼쪽 반, 오른쪽 반으로 나눈다. 왼쪽 반을 정렬하는 부분 문제랑 오른쪽 반을 정렬하는 부분 문제로 나누어 주는 것이다.
Conquer 단계에서는 왼쪽 리스트와 오른쪽 리스트를 각각 정렬해 준다.
Combine 단계에서는 정렬된 두 리스트를 하나의 정렬된 리스트로 합병한다.
두 리스트를 하나로 Combine 할 때가 중요하다. 이미 정렬되었다고 가정하였을때 왼쪽이 제일 작게 정렬했다고 생각하자. 그럼 왼쪽과 오른쪽의 첫번째 값을 비교해 주어서 더 작은 것을 Combined된 리스트에 넣어준다.
계속 하나씩 작은것부터 차례대로 넣어주면 한쪽 리스트만 남을거이다. 이것은 이미 정렬되어 있는 것이기 때문에 남은 것을 왼쪽부터 넣으면 된다. 이렇게 하면 하나의 정렬된 리스트가 된다.
def merge(list1, list2):
i = 0
j = 0
# 정렬된 항목들을 담을 리스트
merged_list = []
# list1과 list2를 돌면서 merged_list에 항목 정렬
while i < len(list1) and j < len(list2):
if list1[i] > list2[j]:
merged_list.append(list2[j])
j += 1
else:
merged_list.append(list1[i])
i += 1
# list2에 남은 항목이 있으면 정렬 리스트에 추가
if i == len(list1):
merged_list += list2[j:]
# list1에 남은 항목이 있으면 정렬 리스트에 추가
elif j == len(list2):
merged_list += list1[i:]
return merged_list
# 테스트
print(merge([1],[]))
print(merge([],[1]))
print(merge([2],[1]))
print(merge([1, 2, 3, 4],[5, 6, 7, 8]))
print(merge([5, 6, 7, 8],[1, 2, 3, 4]))
print(merge([4, 7, 8, 9],[1, 3, 6, 10]))
수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.
산술평균 : N개의 수들의 합을 N으로 나눈 값
중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
최빈값 : N개의 수들 중 가장 많이 나타나는 값
범위 : N개의 수들 중 최댓값과 최솟값의 차이
N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.
출력
첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.
둘째 줄에는 중앙값을 출력한다.
셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.
넷째 줄에는 범위를 출력한다.
예제 입력 1
5 1 3 8 -2 2
예제 출력 1
2 2 1 10
예제 입력 2
1 4000
예제 출력 2
4000 4000 4000 0
예제 입력 3
5 -1 -2 -3 -1 -2
예제 출력 3
-2 -2 -1 2
[문제 해설]
문제에서 구할 것이 꽤 많다. 평균, 중앙값, 최빈값, 최대값과 최솟값의 차이이다. 하나씩 해결해 나가면 된다.
먼저 1번부터 구해보자.
n = int(sys.stdin.readline())
datas=[]
for _ in range(n):
datas.append(int(sys.stdin.readline()))
def first(datas):
return round(sum(datas)/len(datas))
여기서 까다로운 점은 소수점 첫째 자리에서 반올림한 값을 출력해야된다는 것이다. round함수를 사용하자. round함수에서 두번째 인수를 생략하면 앞에 인자에 가장 가까운 정수를 출력한다. 소수 첫째자리에서 반올림하고 싶은 것을 해결해 줄 수 있다.
3번은 어떻게 풀지 감이 아예 오지 않았다. 배열을 2개씩 만들어서도 풀려고 했는데 계속 실패하였다.
찾아보니 최빈값은 모듈을 이용해서 쉽게 해결할 수 있었다.
collections모듈에서 Counter클래스를 사용하는 것이다. 데이터의 개수를 셀 때 파이썬의 collections모듈의 Counter클래스가 유용하다.
Counter클래스는 파이썬의 기본 자료구조인 사전형을 확장하고 있기 때문에, 사전에서 제공하는 API를 그대로 사용할 수 있다. Counter 클래스는 데이터의 개수가 많은 순으로 정렬된 배열을 리턴하는 most_common이라는 메서드를 제공하고 있기 때문에 최빈값을 구하는데 사용할 수가 있다.
def third(datas):
mode_dict = Counter(datas)
modes = mode_dict.most_common()
if len(datas) > 1:
if modes[0][1] == modes[1][1]:
mod = modes[1][0]
else:
mod = modes[0][0]
else:
mod = modes[0][0]
return mod
modes[0][1]은 datas에서 제일 많이 나온 값의 개수를 의미 한다. 최빈값이 여러 개일 경우 두번째로 작은 값을 출력하라고 했으니 modes[0][1] == modes[1][1]일때 modes[1][0]을 출력하고 그렇지 않을때는 modes[0][0]을 출력하면 된다.
4번은 최대값에서 최소값을 빼면 된다.
모든 코드는 아래와 같다.
from collections import Counter
import sys
n = int(sys.stdin.readline())
datas=[]
for _ in range(n):
datas.append(int(sys.stdin.readline()))
def first(datas):
return round(sum(datas)/len(datas))
def second(datas):
datas.sort()
mid = (len(datas))//2
return datas[mid]
def third(datas):
mode_dict = Counter(datas)
modes = mode_dict.most_common()
if len(datas) > 1:
if modes[0][1] == modes[1][1]:
mod = modes[1][0]
else:
mod = modes[0][0]
else:
mod = modes[0][0]
return mod
def fourth(datas):
return max(datas)-min(datas)
print(first(datas))
print(second(datas))
print(third(datas))
print(fourth(datas))
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai≤ 1,000,000, A1= 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
예제 입력 1
10 4200
1
5
10
50
100
500
1000
5000
10000
50000
예제 출력 1
6
예제 입력 2
10 4790
1
5
10
50
100
500
1000
5000
10000
50000
예제 출력 2
12
[문제 해설]
n종류의 동전으로 k금액을 만들면 된다. 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 된다. 그것은 바로 '가장 큰 화폐 단위부터' 나누어 주는 것이다. 물론 k보다 큰 금액이면 나눌 수 없으므로 k보다 작은 것중에 제일 큰 수부터 나누면 된다.
n,k=map(int,input().split())
a=[]
for _ in range(n):
a.append(int(input()))
a.sort(reverse=True)
ans=0
for i in range(n):
if a[i]>k:
continue
else:
ans+=k//a[i]
k=k%a[i]
print(ans)
그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 많다.
사실 그냥 머리에 떠올린대로 그리디 해법을 생각했을때 해법이 정당한지 컴토해야 한다. 여기서 그리디 알고리즘을 검증하려면 조건을 유심히 봐야된다.
괄호 안에 주어진 조건을 자세히 살펴보자. 이 문제에서는 조건이 중요하다.
(1 ≤ Ai≤ 1,000,000, A1= 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) Ai는 Ai-1의 배수라는 점. 그리디 알고리즘의 정당성을 부여하려면 예시를 들어보자. 만약 k의 값이 800원이고 Ai 배열에서 500원, 400원, 100원이라면 우리가 짠 그리디 알고리즘으로는 500원 1개, 100원 3개가 최적의 답으로 나온다. 그러나 사실 400원 2개 주는 것이 더 이득이다. 이 문제는 다이나믹 알고리즘으로 따로 풀 수 있다.
이 문제에서 그리디 알고리즘을 쓸 수 있었던것은 Ai는 Ai-1의 배수라는 사실 때문이다.
문제가 길지만 정리하자면 배추밭에서 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)
방향 없는 그래프가 주어졌을 때, 연결 요소 (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으로는 시간초과가 난다. 그래서 질문을 올렸더니...
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 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)
