코테 준비 - 그래프 1

백준 2606 바이러스

입력

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

출력

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

예제 입력 1 복사

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

 

예제 출력 1 복사

4

이걸 맨날 구현하면서만 배웠는데 함수로 사용하는 법을 몰라서...

파이썬은 이름만 que, deque라고 하지 자료형을 편하게 사용할 수 있으니까 막 쓰네요?

visited = [0]*(N+1)
cnt = 0
def DFS(a):
    visited[a]=1

    for i in network[a]:
        if (visited[i]==0):
            DFS(i)
            cnt+=1
            
def BFS(a):
    visited[a] = 1
    queue = [a]
    while queue:
        for i in network[queue.pop()]:
            if (visited[i]==0):
                visited[i]=1
                queue.insert(0, i)
                cnt+=1

음...

오랜만에 BFS,DFS를 봤는데 파이썬은 되게 쉽게 구현하네요 ㅎ...

 

백준 1012 유기농 배추

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

예제 입력 1 복사

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

예제 출력 1 복사

5
1

예제 입력 2 복사

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

예제 출력 2 복사

2

지렁이는 상하좌우까지해서 5칸을 지킬 수 있다!

아 그게 아니라 그렇게 해서 움직일 수 있으니까 나뉘어져 있는 그룹이 몇개인지 확인하면 되는 거네요 ....

 

백준 1260  DFS, BFS

문제

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

입력

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

 

출력

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

 

예제 입력 1 복사

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

예제 출력 1 복사

1 2 4 3
1 2 3 4

예제 입력 2 복사

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

예제 출력 2 복사

3 1 2 5 4
3 1 4 2 5

예제 입력 3 복사

1000 1 1000
999 1000

예제 출력 3 복사

1000 999
1000 999

바로 받아서 어떻게 갈까 생각해보니까 그럼 계속 정렬이 필요하더라고여

그래서 어떻게 하지 했는데 커다란 행렬을 하나 만들면 금방 되네요...

 

백준 4963 섬의 개수

입력

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

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

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

출력

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

예제 입력 1 복사

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

예제 출력 1 복사

0
1
1
3
1
9

지렁이 문제랑 똑같습니다.

DFS진행하면서 지나간 곳은 바다로 만들고, 끝나면 카운터 하나 늘려서 섬임을 확정하기!

ㅇㅋ 다들 이렇게 했네요 BFS는 큐를 만들어야 해서 나중에 구현하고 당장 할 수 있는 DFS로 집중해서 하기

 

백준 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

이것도 연결 안된 것 구하기네요

 많이 배우고 가네요... 재귀 함수의 깊이도 제한이 있어서 오류나는 것을 처음 배웠씁니다...

import sys
sys.setrecursionlimit(10000)  # 재귀 호출 깊이 한계를 10000으로 설정

n, m = map(int, input().split())
graph = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    x, y = map(int, input().split())
    graph[x][y] = graph[y][x] = 1

cnt = 0
visit = [False] * (n + 1)  # 방문하지 않은 상태를 False로 표시

def DFS(a):
    if visit[a]:  # 이미 방문했으면 더 이상 탐색하지 않음
        return
    visit[a] = True  # 현재 노드를 방문 처리
    for i in range(1, n + 1):  # 0을 제외한 1부터 시작
        if graph[a][i] == 1 and not visit[i]:  # 인접하고 아직 방문하지 않은 노드
            DFS(i)  # 인접 노드로 DFS 재귀 호출

for i in range(1, n+1):  # 0을 제외한 1부터 시작
    if not visit[i]:
        DFS(i)
        cnt += 1
print(cnt)

근데 아직도 DFS깊이가 너무 깊은가 본디....

시간 초과가 뜨네요 ㅎㅎ... ㅠ

BFS?

graph = [[] for _ in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

그래프를 이렇게 구현하면 굳이 힘들게 배열을 다 쓰지 않아도 되네여...

 

백준 11725 트리의 부모 찾기

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

4
6
1
3
1
4

예제 입력 2 복사

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2 복사

1
1
2
3
3
4
4
5
5
6
6

?????

문제부터 이해가...?

사진을 보면 이해가 좀 되네요

루트가 그 뿌리라고 생각해서 제일 밑이라고 생각해 버렸던... 자료구조 한지 몇달 안지났는데....

 

백준 24479 알고리즘 수업 - 깊이 우선 탐색

문제

오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.

깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.

dfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
    for each x ∈ E(R)  # E(R) : 정점 R의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
        if (visited[x] = NO) then dfs(V, E, x);
}

입력

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.

다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

출력

첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서는 1이다. 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

1
2
3
4
0

import sys
sys.setrecursionlimit(10000)  # 재귀 호출 깊이 한계를 10000으로 설정


n, m, r = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

visit = [0] * (n+1)

def dfs(a):
    if visit[a] == 1:
        return
    print(a)
    visit[a] = 1
    for i in graph[a]:
        if visit[i] == 0:
            dfs(i)

dfs(r)

내일 이 시험이라 급히급히 배우는데 어우

이것도 재귀함수가 너무 깊이 들어간다고 하네요 ㅎ....

시작 정점에서 방문하지 못하는 경우는 0이라고 한다 했으니 그거 처리를 해줘야 겠네요....

아 방문한 정점을 출력하는게 아니라 i번째를 언제 방문하는지를....

런타임 에러 (UnboundLocalError) : 함수에서 전역, 로컬 변수 오

이런 오류도 처음 봤네요

입력에 어떤 함수를 쓰냐에 따라 또 속도 차이도 나네요...

import sys
sys.setrecursionlimit(10**6) 

count = 1
n, m, r = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

for i in range(1, len(graph)):
    graph[i].sort()
    
visit = [0] * (n+1)

def dfs(a):
    global count
    visit[a] = count
    count += 1
    for i in graph[a]:
        if visit[i] == 0:
            dfs(i)

dfs(r)
for i in range(1 , n+1):
    print(visit[i])