본문 바로가기

dfs

[백준 9663] N-Queen(JAVA)

CodingTEST 2024. 2. 11. [백준 9663] N-Queen(JAVA) 백준 9663번 문제 - N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓을 수 있는 방법의 수 해결 포인트 퀸이 공격할 수 있는 범위 상하좌우, 대각선 칸 수 제한 없이 무제한 ! DFS 사용 가로, 세로 줄은 단순하게 퀸이 놓아졌으면 놓기 금지 - 가로,세로 확인할 수 있는 배열 구현 가로 row[N] 세로 col[N] 퀸을 놓은 곳의 가로, 세로 위치를 true로 설정 퀸 위치 x,y일 때, row[x] = true; col[y] = t..

[백준 1967] 트리의 지름(JAVA)

CodingTEST 2024. 2. 11. [백준 1967] 트리의 지름(JAVA) 백준 1967번 문제 - 트리의 지름 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 분석 트리(tree) 사이클이 없는 무방향 그래프이다. 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리의 지름 : 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이 트리의 지름을 출력해라. 해결 포인트 DFS 사용 DFS는 최장 값을 반환 1부터 N까지 반복하면서 모든 위치에서 시작하는 DFS를 실행 코드 import java.io.*; import java.util..

[백준 14503] 로봇 청소기 (JAVA)

CodingTEST 2023. 11. 23. [백준 14503] 로봇 청소기 (JAVA) 백준 14503번 문제 - 로봇 청소기 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 분석 로봇청소기가 청소하는 영역의 개수 출력 처음 지정받은 칸도 청소함 주변 4칸 중 청소할 칸이 있음 : 90도로 반시계방향으로 돌아서 청소해야하면 청소 (아니면 계속 돌기) 주변 4칸 중 청소할 칸이 없음 : 뒤에 벽이 없을 경우 뒤로 후진한다. 벽이 있을 경우 청소기를 멈춘다. 해결 키 포인트 DFS 사용 처음 지정받은 칸도 청소함 : count 초기값 1 주변에 ..

[백준 1033] 칵테일 (JAVA)

CodingTEST 2023. 8. 17. [백준 1033] 칵테일 (JAVA) 백준 1033번 문제 - 칵테일 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 문제 분석 N개의 수와 N-1개의 비율을 입력받고, 그들을 통해 구해진 N개의 최소 배율을 출력해라 N-1개의 비율 입력(a,b,p,q) : a/b = q/p 해결 키 포인트 유클리드 호제법을 이용해 최대 공약수,최소 공배수를 구한다 최소 공배수: DFS를 설정하기 시작할 때, 이용 - 비율(분자, 분모)의 최소 공배수의 곱을 초기값으로 최대 공약수: 최소 배율을 출력해야하므로, 모든 배율 값의 최대 공약수를 구해 이용 DFS 사..

[백준 1167] 트리의 지름 (JAVA)

CodingTEST 2023. 8. 11. [백준 1167] 트리의 지름 (JAVA) 백준 1167번 문제 - 트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 분석 정점을 입력 받는다 어떤 정점의 간선을 입력 받을 지 먼저 입력 | 간선으로 이어질 정점 | 간선까지의 거리를 입력 | (반복) | -1 1 3 2 -1 입력받은 정점들 간의 거리 중 가장 긴 거리를 출력해라 해결 키 포인트 DFS(깊이 우선 탐색) 개념 파악 정점의 간선을 순서대로 입력 받는게 아니라, 맨 앞에 정점을 선언하여 불규칙적으로 입력 받을 수 있다 ex) 2 4 4 -1 1 3 2 -1..

[백준 1260] DFS와 BFS (JAVA)

CodingTEST 2023. 8. 9. [백준 1260] DFS와 BFS (JAVA) 백준 1260번 문제 - DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 분석 정점 수와 간선, 그리고 시작할 노드를 입력받는다. 이를 토대로 해당 노드에서 시작했을 때 DFS와 BFS를 출력한다. 해결 키 포인트 DFS(깊이 우선 탐색) 개념 파악 BFS(너비 우선 탐색) 개념 파악 깊이 우선 탐색(DFS) 그래프 완전 탐색 기번 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 ..

[백준 2023] 신기한 소수 (JAVA)

CodingTEST 2023. 8. 6. [백준 2023] 신기한 소수 (JAVA) 백준 2023번 문제 - 신기한 소수 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제 분석 자리수가 입력되면 해당 자리 수 중에서 다음 조건을 만족하는 수(신기한 소수)들을 출력해라 N번자리부터 오른쪽으로 0부터 N-1까지 숫자를 같이 봤을 때 모든 수가 다 소수인 수 ex) N = 4 | 주어진 숫자 = 2333 일 때 해당 수는 신기한 소수에 포함 (다음 표 참고) i N부터 i까지 오른 쪽 숫자 소수 판별 0 2 O 1 23 O 2 233 O 3 2333 O 해결 키 포인트 DFS(깊이 ..

[백준 11724] 연결 요소의 개수 (JAVA)

CodingTEST 2023. 8. 3. [백준 11724] 연결 요소의 개수 (JAVA) 백준 11724번 문제 - 연결 요소의 개수 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 문제 분석 입력된 간선들을 토대로 정점들의 연결을 알아내, 연결 요소의 개수를 알아내 출력 해결 키 포인트 DFS(깊이 우선 탐색) 개념 파악 연결 요소 개념 파악 연결 요소: 각 노드들이 뭉쳐진 묶음 개수 간선을 입력받아서 각 정점에 존재하는 연결 노드를 알아내야 한다. 해당 정보를 가지고, 후에 연결 요소 개수를 알 수 있다. 모든 정점을 확인했는지 판..

이전 1 다음

티스토리툴바