이것저것 개발 블로그

https://www.acmicpc.net/problem/11725

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main_BJ_11725_트리의부모찾기 {
    static ArrayList<Integer>[] list;
    static int n;
    static int[] parents;
    static boolean[] visited;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        list = new ArrayList[n+1];
        parents = new int[n+1];
        visited = new boolean[n+1];

        for(int i=1; i<=n; i++)
            list[i] = new ArrayList<Integer>();

        for(int i=1; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            list[start].add(end);
            list[end].add(start);
        }

        dfs(1);
        for(int i=2; i<=n; i++)
            System.out.println(parents[i]);
    }//main
    private static void dfs(int p){
        visited[p] = true;
        for(int i=0; i<list[p].size(); i++){
            if(!visited[list[p].get(i)]){
                parents[list[p].get(i)] = p;
                dfs(list[p].get(i));
            }
        }
    }//dfs
}

dfs를 사용해서 문제를 풀어봤다.

1. 연결 리스트를 활용해 연결된 노드들을 모두 적어준다.(단방향이 아니므로 양방향으로 넣어준다)

2. 루트 노드는 1이므로 1로 시작!

3. dfs를 돌리는 노드는 방문 처리후, 해당 노드에 연결된 친구들을 본다.

4. 방문하지 않은 노드를 dfs로 다시 돌려주는데, 현재 있는 노드가 다음 dfs를 돌릴 노드의 부모이므로, 배열에 저장해준다.

5. 모든 노드가 방문처리 되어 끝났다면 출력해주면 된다!

나름 간단한 문제였다!!

https://www.acmicpc.net/problem/2606

문제)

풀이)

def dfs(x):
    global visited
    if visited[x] == False:
        visited[x] = True
        for i in graph[x]:
            dfs(i)
    else:
        return 0

n = int(input())
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
li = int(input())

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

count = 0
dfs(1)
for i in range(2, len(visited)):#1번은 제외
    if visited[i] == True:
        count += 1
print(count)

이 문제는 dfs로 해결했는데, 간단한 문제이다. 물론 bfs로도 충분히 가능할 것이다.

무조건 1번에서 시작하므로 1번 노드에서 각 노드를 방문 표시한 개수를 센다면 문제를 해결할 수 있을 것이라고 생각했다.

따라서 입력으로 그래프를 생성하고(이때 그래프는 i번 노드에 연결된 노드를 모두 저장한다.),

DFS를 이용하여 1번에서 연결된 노드를 방문 표시해준다.

마지막으로 방문 표시한 개수를 세는데, 본인 노드(1번 노드)는 카운트하지 않으므로 2번 노드부터 끝까지 방문 표시된 노드 개수를 센다.

DFS(Depth-First Search, 깊이 우선 탐색)

그래프에서 깊은 부분을 우선적을 탐색하는 알고리즘. 스택(stack)을 사용한다!

동작 과정:

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

2번 과정에서 방문하지 않은 인접 노드를 스택에 넣을 때 순서는 상관없지만, 문제에 따라서 알파벳 순서 또는 작은 숫자 순서대로 가는 경우가 많으므로 작은 노드 순서대로 넣는 경우가 많다.

그럼 실습해보자!!

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],
    [1, 5],
    [1, 4],
    [3],
    [2, 6, 7],
    [1, 5],
    [5]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 8
# DFS 호출
dfs(graph, 1, visited)


### 출력 결과(stack에 들어간 순서대로): 1 2 5 6 7 3 4

BFS(Breath-First Search, 너비 우선 탐색)

가까운 노드부터 탐색하는 알고리즘. 큐(queue)를 사용한다!

동작 과정:

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

BFS와 마찬가지로 작은 노드부터 수행하는 경우가 많다!

위에 있는 그래프를 이용하여 다시 실습해보자!

from collections import deque

# BFS 정의
def bfs(graph, start, visited):
    # queue 구현 위해 deque 라이브러리 사용
    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차원 리스트)
graph = [
    [],
    [2, 3],
    [1, 5],
    [1, 4],
    [3],
    [2, 6, 7],
    [1, 5],
    [5]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 8
# BFS 호출
bfs(graph, 1, visited)


### 출력 결과(큐에 삽입된 순서대로): 1 2 3 5 4 6 7