DFS 이진트리 순회 [전위순회, 중위순회, 후위순회] with Java

들어가며DFS 알고리즘을 이용한 이진트리 순회과정을 코드로 구현하고 그림을 통해 이해하려고 한다. 순회의 방문 순서는 다음과 같다.전위순회 : root, left, right중위순회 : left, root, right후위순회 : left, right, root즉 root의 위치가 어딨는지에 따라 다르므로 root 기준으로 생각하면 된다. 코드 구현먼저 하나의 Node라는 객체를 생성해야 한다.Node 는 하나의 정점이라고 생각하면 된다.Node 는 field로 data, left, right 를 가지는데 left, right를 연결된 노드라고 생각하면 된다. class Node { int data; Node lt; Node rt; public Node(int data) { ..

• format_list_bulleted Algorithm
• · 2024. 8. 9.
• textsms

Java 정렬 방법 정리 [Comparator vs Comparable]

Comparator vs Comparable처음엔 이해가 안될 수 있으니 밑에 예제들을 참고해주세요.특징ComparableComparator정의 위치클래스 내부클래스 외부정렬 기준의 수단일 정렬 기준다수의 정렬 기준주요 메서드compareTo(T o)compare(T o1, T o2)용도기본 정렬 기준을 정의할 때 사용다양한 정렬 기준을 정의할 때 사용구현 방식public class ClassName implements ComparableComparator comparator = new Comparator() { ... };자주 사용되는 경우자연스러운 순서를 정렬해야 할 때특정 상황에 따라 다른 기준으로 정렬할 때예시public int compareTo(Person other) { return this...

• format_list_bulleted Algorithm
• · 2024. 7. 30.
• textsms

7562 백준 파이썬 [나이트의 이동]

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 이문제는 BFS를 이용해 l * l 맵 에서 처음가보는 장소가 있다면 직전거리(graph)에다 + 1을해가며 (visited)방문처리를 해주었다. 마지막으로 graph[e_y][e_x]를 해주면 목표지점의 거리가 나올것이다. from collections import deque import sys input = sys.stdin.readline dx = [2, 2, -2, -2, 1, -1, 1, ..

• format_list_bulleted Algorithm
• · 2023. 2. 20.
• textsms

[백준 / 파이썬] 2573 빙산

BFS 함수를 2개만들었다. 1. 1년마다 녹는걸 구현하는 BFS 2. 그 후에 몇덩이로 나눠졌는지 확인하는 BFS를 구현했다. 까다로웠던 부분은 첫번째 BFS에서 바다인 부분은 방문처리를 하면 안된다는 부분이다. 왜냐면 빙산은 상하좌우 빙하의 개수에 의해 깎여나가는데 바다를 방문처리해서 들리지 않게 된다면 깎이는 부분이 적어지기 때문이다. from collections import deque n, m = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(n)] dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] time = 0 def bfs(a, b): global time visited =..

• format_list_bulleted Algorithm
• · 2023. 2. 5.
• textsms

[백준] Python 2667 단지번호붙이기 DFS/BFS

모든 행, 열을 완전탐색하여 1인곳을 찾아 DFS 혹은 BFS로 들어가면된다. BFS 좀 해메었지만 원리는 단순하다. 방문처리가 필요없이 방문한 곳들을 0으로 만들어 주고 cnt를 늘리는 방식으로 단지가 몇개인지 세면된다. from collections import deque n = int(input()) graph = [list(map(int, input())) for _ in range(n)] # 모든 인덱스를 확인하여 1이 있으면 bfs로 지난부분 0으로 만들기., 다 파고들면 다시 방문안한 1부터 dfs house = [] dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] def bfs(r, c): q = deque() q.append((r, c)) graph[r][c] = 0 ..

• format_list_bulleted Algorithm
• · 2023. 2. 4.
• textsms

[백준] Python 2606 바이러스 BFS/DFS로 풀이.

먼저 DFS 풀이. 방문한 노드면 재귀 종료. 방문 안한 노드면 방문처리 해주고 연결된 노드들 확인. from collections import defaultdict n = int(input()) connect_len = int(input()) dic = defaultdict(list) for i in range(connect_len): a, b = map(int, input().split()) dic[a].append(b) dic[b].append(a) # 양방향 # dfs 접근 visited = [False for _ in range(n+1)] # 1번부터 시작하기 위해 n+1 def dfs(v, visited): global cnt if visited[v]: return visited[v] = Tr..

• format_list_bulleted Algorithm
• · 2023. 2. 4.
• textsms