본문 바로가기

Problem Solving1486

[백준] 11403 경로 찾기 - Graph Theory / Java • 문제 링크 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net • 풀이 과정 모든 정점에서 모든 정점으로의 최단 거리를 구하고 정점의 개수가 1 ≤ N ≤ 100 수준이므로 플로이드 와샬 알고리즘을 활용하여 풀이한다. 기본적으로 거쳐가는 정점을 기준으로 최단 거리를 구하며 거쳐가는 정점이 k 일 경우 i 에서 j 로 도달하는 거리와 i 에서 k를 거쳐 k 에서 j 로 도달하는 거리는 같다는 전제를 둔다. 즉 k, i, j 의 3중 for문 내에서 arr[i][k] == 1 && arr[k][j] == 1 인 경우에만 arr[i][j] = 1 로 모든 정.. 2022. 7. 14.
[백준] 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.

티스토리툴바