백준(11724, 2023, 13023)

그래프 탐색(깊이 우선 탐색)

연결요소의 개수 구하기(11724)

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

• 입력

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

• 입출력 예시

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

-------------------

2

해결책

1. 방향성이 없는 그래프 탐색임에 주의하자.
2. 재귀함수를 이용한 깊이우선탐색을 실시한다.
   1. 방문 리스트를 만들어서 방문 시 true 재방문시 접근하지 못하도록 한다.
3. Main에서 연결요소의 개수를 센다.
   1. 깊이우선탐색을 할때마다 방문 배열을 check한다.

코드

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
def dfs(cur,maps):
    
    if visited[cur]:
        return
    else :
        visited[cur]=1
        for i in maps[cur]:
            if not visited[i]:
                dfs(i,maps)
    

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

visited=[0]*(n+1)
maps={}
for i in range(n):
    maps[i+1]=[]

for i in range(m):
    start,end=map(int,input().split())
    maps[start].append(end) # 양방향이 가능하다록 한다.
    maps[end].append(start)
cnt=0
for i in range(n):
    if not visited[i+1]:
        cnt+=1
        dfs(i+1,maps)
print(cnt)

신기한 소수 찾기(2023)

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

• 입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

• 입출력 예시

4

-------------------

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

해결책

1. n의 자리값까지 깊이 우선탐색한다. (*10+(자릿수))
   1. 10이하의 수 중 소수는 2,3,5,7이므로 시작 노드값을 제한한다.
   2. 재귀함수내에서 2,4,6,8,0은 무조건 소수가 될 수 없다.
   3. 깊이가 입력(n)이랑 같아지면 print해준다.
      1. 오름차순으로 정렬할 필요 없이 순차적으로 그래프 탐색하기 때문에 따로 정렬을 할 필요없다.
2. 소수판별은 N/2까지만 검토하면된다.

코드

import sys
sys.setrecursionlimit(10000)
input =sys.stdin.readline

def isPrime(num):
    for i in range(2,int(num/2+1)):
        
        if num%i==0:
            return False
        
        
    return True

def dfs(cur,f):
    if f==N:
        print(cur)
    else :
        

        for i in range(1,10):
            if i % 2 ==0:
                continue
            
            
            if isPrime(cur*10+i):
                dfs(cur*10+i,f+1)
            
    
N=int(input())
ls = [2,3,5,7]
for i in ls:
    dfs(i,1)

ABCDE(13023)

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

• 입출력 예시

5 4
0 1
1 2
2 3
3 4

-------------------

1

해결책

1. 재귀를 활용한 깊이우선탐색을 진행한다.
   1. 방문할때마다 방문배열에 check를 하고 깊이가 5까지 진행할 수 없으면 return한다.
   2. 이미 방문한 노드만이 연결되어있거나, 리프노드일경우 현재방문노드의 방문배열에 false를 집어넣는다.

코드

import sys
sys.setrecursionlimit(10000)
arrive = False
def dfs(cur,depth):
    global arrive
   
    if visited[cur]:
        
        return
    else :
        if depth == 5:
            arrive=True
            return
            
        
        visited[cur]=1
        for i in maps[cur]:
            if not visited[i]:
                dfs(i,depth+1)
        visited[cur]=0
    

n,m=map(int,sys.stdin.readline().split())

visited=[0]*(n+1)
maps={}
for i in range(n):
    maps[i]=[]

for i in range(m):
    start,end=map(int,sys.stdin.readline().split())
    maps[start].append(end)
    maps[end].append(start)
for i in range(n):
    if arrive == True:
        break
    dfs(i,1)
    
if arrive :
    print(1)
else:
    print(0)