본문 바로가기

Problem Solving1214

[백준] 7562 나이트의 이동 - Graph Theory / Java • 문제 링크 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net • 풀이 과정 나이트의 이동을 구현할 방향 배열을 8방향으로 설정해둔다. 시작점과 도착점을 매개변수로 받아 bfs 탐색을 수행하며 시작점을 큐에 삽입 및 방문했음을 표시하기 위해 1로 값을 지정한다. 일반적인 bfs 탐색을 수행하되 각 다음 방문할 위치마다 현재 위치의 값 + 1 을 설정하여 해당 위치에 도달하기까지 몇 번을 이동했는지 나타낸다. 현재 위치가 도착점일 경우 bfs 함수를 빠져나가고 처음 시작점을 방문했음을 표시하기 위해 1로 설정했고.. 2022. 7. 12.
[백준] 4963 섬의 개수 - Graph Theory / Java • 문제 링크 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net • 풀이 과정 [백준] 11724 연결 요소의 개수 - Graph Theory / Java • 문제 링크 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, graycode.tistory.com 위의 문제와 유사한 연결 요소의 개수를 구하는 문제. 다른 점은 2차원 배.. 2022. 7. 11.
[백준] 11724 연결 요소의 개수 - Graph Theory / Java • 문제 링크 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 • 풀이 과정 무향 그래프의 정점이 모두 연결되어 있고 하위 그래프와 나머지 그래프 사이에 연결이 없을 경우, 이를 연결 요소라 명칭하며 아래의 예시에서는 (0, 1, 2, 3), (4, 5, 6), (7, 8) 총 3개의 연결 요소가 존재한다. 이러한 연결 요소의 개수는 dfs / bfs 로 탐색하여 구할 수 있으며 해당 문제에선 연결 리스트를 활용한 dfs로 풀이하였다. 모든 노드를 .. 2022. 7. 10.
[백준] 16198 에너지 모으기 - Backtracking / Java • 문제 링크 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net • 풀이 과정 구슬을 선택함에 따라 해당 구슬이 제거됨을 구현해야 하므로 List 자료구조를 사용한다. list 변수에 입력받은 값을 재귀 호출 함수를 통해 탐색하여 선택한다. 첫 번째와 마지막 인덱스는 제외하여 탐색하고, 값이 제거됨에 따라 첫 번째와 마지막 인덱스만 남았을 시, 즉 리스트의 크기가 2일 시 해당 분기의 탐색을 종료한다. 현재 인덱스의 이전 인덱스, 다음 인덱스의 값을 곱하여 energy 변수에 더한 후 매개변수로 전달하며, .. 2022. 7. 9.
[백준] 10819 차이를 최대로 - Backtracking / Java • 문제 링크 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net • 풀이 과정 방문 여부를 확인하는 재귀 호출 함수로 입력받은 배열의 중복을 허용하지 않은 모든 순열을 구한다. 순열에 문제에 제시된 (arr[0] - arr[1]) + (arr[1] - arr[2]) + ... + (arr[n - 2] - arr[n - 1]) 의 연산을 수행하는데 이는 배열의 현재 인덱스와 다음 인덱스를 뺀 값을 sum 변수에 연속해서 더하며 식의 최댓값을 구하는 순서를 찾기 위해, 뺄셈의 값은 절대값으로 계산한다. 각각의 순열에서 구해진 연산.. 2022. 7. 8.
[백준] 6603 로또- Backtracking / Java • 문제 링크 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net • 풀이 과정 while 문에서 입력의 한 라인을 StringTokenizer 로 받되, 첫 토큰이 0이 아닐 시에만 탐색을 수행한다. 첫 토큰이 곧 문제상 k값이며 int 배열 arr 와 boolean 배열 visit 의 크기를 k 로 생성하고 원소를 저장한다. 해당 배열을 재귀 함수의 깊이가 6일 때까지 호출하여 탐색하며, 인덱스의 방문 여부를 확인하는 방식으로 구한 각각의 순열을 StringBuilder 에 적절히 줄바꿈하여 하나의.. 2022. 7. 7.

티스토리툴바