본문 바로가기

전체 글1321

[백준] 2667 단지번호붙이기 - Graph Theory / Java • 문제 링크 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net • 풀이 과정 0 과 1을 입력받아 단지의 형태를 나타내는 2차원 배열을 생성하고 전체 노드를 탐색하여 0 이 아닌, 즉 방문 가능한 노드를 시작 노드로 하나의 연결 요소로써 탐색한다. 배열의 범위 내의 연결된 노드의 값이 1인 위치을 찾아가며, 방문한 위치마다 0 으로 변경하고 cnt 변수에 1을 더하여 해당 연결요소의 방문한 모든 노드의 개수를 반환한다. 반환한 값은 List 자료구조에 저장되며 최종적으로 연결 요소의 개수를 의미하는 list.s.. 2022. 7. 13.
[백준] 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.

티스토리툴바