반응형
[BOJ 2668] 숫자고르기 (Java, DFS)
알고리즘/그래프 탐색2023. 6. 14. 15:49[BOJ 2668] 숫자고르기 (Java, DFS)

문제 링크 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 문제 풀이 위한 아이디어가 처음 생각나지 않았다. 텀프로젝트(BOJ 9466) 문제 풀이 후 동일하게 visit과 finish배열 활용하여 결과 값을 구할 수 있는 것을 이해하게 되었다. 이런 기법을 어떻게 생각해내는지 대단하다 다들 :) 풀이 - 사이클 발생하거나, 노드가 자신을 가르키는 경우를 구함 - 시간복잡도 : O(N) - (기법*) finish 배열 활용하여 중복..

[BOJ 4803] 트리 (Java, DFS)
알고리즘/그래프 탐색2023. 6. 14. 15:21[BOJ 4803] 트리 (Java, DFS)

문제 링크 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 재귀 함수로 그래프 사이클 판별하는 함수가 이해 되지 않아 몇일 소요 - 재귀 함수를 스택으로 생각 - 이미 방문한 적 있고, 부모 노드가 다른 경우 사이클 발생 (=그래프) 풀이 - 케이스별로 정점 N, 간선 M 이 주어질 때 트리의 개수를 구하여 형식에 맞게 출력하게 됨 - 이때 연결된 간선이 없는 정점 또한 트리 개수로 카운팅함 - 재귀 함수 기법을 활용하여 그래..

[BOJ 15686] 치킨 배달 (Java, DFS)
알고리즘/그래프 탐색2023. 6. 14. 14:22[BOJ 15686] 치킨 배달 (Java, DFS)

문제 링크 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 - 주어진 치킨 집 중에 최대 M개 선택(조합)하여, 도시의 치킨 거리의 최솟값을 출력함 - 집의 개수는 N = 50 일때 최대 100개까지 가능 - 치킨집 개수는 최대 M = 13 1) 초기화 치킨집(2)과 집(1)의 좌표를 담은 리스트 구함 2) 치킨집 조합 구하기 조합 (Combination, nCr) : 서로 다른 n개 중에 r개를 중복없이 뽑음, 이때..

[BOJ 1240] 노드 사이의 거리 (Java, DFS)
알고리즘/그래프 탐색2023. 6. 13. 14:36[BOJ 1240] 노드 사이의 거리 (Java, DFS)

문제 링크 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 풀이 - 인접 리스트로 풀 경우 노드와 연결된 간선 정보만 조회 - 시간 복잡도 : O(V + E), 그리고 M번 반복 - Node 클래스 정의 후 양방향 그래프 표현 예제 입력에 따라 거리 값을 구하면 아래와 같다 # 시작, 끝 = 1, 2 [0, 0, 2, 5, 3] # 시작, 끝 = 3, 2 [0, 5, 7, 0, 2] 제출 코드 import java.util...

[BOJ 14888번] 연산자 끼워넣기 (Java, 완전탐색, 재귀호출)
알고리즘/완전 탐색2023. 6. 13. 12:34[BOJ 14888번] 연산자 끼워넣기 (Java, 완전탐색, 재귀호출)

문제 링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 풀이 - DFS로 연산자에 대한 순열(Permutation)을 구한 후 연산 결과값 구함 - N(2 ≤ N ≤ 11) 이므로 최대 연산자 개수는 10개, 순열 10! = 3,628,800 - 시간복잡도 O(N! * N ) = O(10! * 11) = 약 3,600만번 이므로 풀이가능 제출 코드 풀이1. 연산자 순열을 구한 후 연..

[BOJ 10819] 차이를 최대로 (Java, DFS)
알고리즘/그래프 탐색2023. 6. 13. 11:49[BOJ 10819] 차이를 최대로 (Java, DFS)

문제 링크 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 풀이 - 순열 (permutation) : N개 중 중복없이 N개를 나열하였을 때 최대값을 구함 - 최대치 8P8 = 8! = 40320 이기 때문에 DFS 로 구현 가능 예제 입력 1에 대한 순열을 구할 경우 아래와 같은 형태로 나옴 #입력 6 20 1 15 8 4 10 #순열의 경우 [20, 1, 15, 8, 4, 10] [20, 1, 15, 8, 10, 4] [20, 1, 15, 4, 8, 10..

[BOJ 5214] 환승 (Java, BFS)
알고리즘/그래프 탐색2023. 6. 12. 16:47[BOJ 5214] 환승 (Java, BFS)

문제 링크 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 풀이 - 역의 수 N, 한 하이퍼 튜브가 서로 연결하는 역의 개수 K, 하이퍼 튜브의 개수 M이 주어짐 (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) - 시간복잡도 O(V + E) 실패* 처음에 연결한 역 번호를 가지는 하이퍼 튜브와 연결된 하이퍼 튜브 번호를 가진 역 노드를 생각해서 List 2개 선언하여 풀었는데 '시간초과' 발생 확인 아이..

[BOJ 1707] 이분 그래프 (Java, BFS)
알고리즘/그래프 탐색2023. 6. 12. 15:43[BOJ 1707] 이분 그래프 (Java, BFS)

문제 링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 - BFS 로 각 노드에 대한 색상 (0, 1)을 번갈아 가며 지정 - 이때 연결된 노드의 색상이 동일한 경우 이분 그래프가 아님 - 테스트 케이스별로 BFS 탐색시 시간 복잡도 O(V + E) 만큼 시간 소요 실수 - 양방향 그래프 설정을 하지 않고 탐색을 해서 틀림 이분그래프 개념 참고 https://gmlwjd9405.github.io/2018/08/23/algorithm-b..

[BOJ 14395] 4연산 (Java, BFS)
알고리즘/그래프 탐색2023. 6. 12. 14:06[BOJ 14395] 4연산 (Java, BFS)

문제 링크 https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 풀이 - BFS 그래프 탐색 문제 - 첫 줄에 S, T 가 주어짐 (1 ≤ s, t ≤ 10^9) - 현재 값과 연산자를 담은 Object를 정의해서 Queue에 담아 처리하도록함 에러 - 만약 배열 선언시 최대 10^9 까지 있기 때문에 '메모리 초과' 발생 - 나누기(/) 연산시 값이 0 인 경우 '/ by zero' 에러 발생 실수 - Set을 사용하여 이미 구한 값 여부 ..

[BOJ 16953] A -> B (Java)
알고리즘/그래프 탐색2023. 6. 12. 13:11[BOJ 16953] A -> B (Java)

문제 링크 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A A 로 감소 시키면서 카운팅 처리하도록 풀이 1) 2 를 곱하는 경우는 => 2로 나누어지는 경우 2로 나누기 2) 끝자리에 1을 붙이는 경우는 => 끝자리가 1인 경우 10 으로 나누기 (*Java 에서는 실수값 나누기할 경우 실수만 취급) *실수 B 값이 2로 나누어지지 않거나, 끝자리가 1이 아닌 경우는 답을 구할 수 없으므..

[BOJ 18405] 경쟁적 전염 (Java, BFS)
알고리즘/그래프 탐색2023. 6. 12. 12:20[BOJ 18405] 경쟁적 전염 (Java, BFS)

문제 링크 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 - N * N 행렬 주어짐 (K 는 바이러스 번호인데, 사용하지 않음) - 상,하,좌,우 격자형 그래프 탐색 문제 - 아래 조건에 따라 바이러스는 번호와 초에 따라 정렬된 상태에서 탐색이 진행되야 함 (*실수 부분) 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다 - 따라서 Java에서 제공하는 우선 순위 큐(PriorityQueue) ..

[BOJ 18352] 특정 거리의 도시 찾기 (Java, BFS)
알고리즘/그래프 탐색2023. 6. 12. 12:00[BOJ 18352] 특정 거리의 도시 찾기 (Java, BFS)

문제 링크 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 - BFS 활용하여 X 부터 다른 노드까지의 거리 배열 구한 후 K에 해당하는 거리값을 가지는 노드 오름차순으로 풀이 - 간선의 비용이 1이기 때문에 최단 거리가 아닌 BFS 만으로도 풀이 가능 *실수 1) 거리 배열(DIST)를 최대값으로 초기화 하지 않은 것 Arrays.fill(DIST, Integer...

[BOJ 7569] 토마토 (Java, 그래프 탐색)
알고리즘/그래프 탐색2023. 6. 9. 23:16[BOJ 7569] 토마토 (Java, 그래프 탐색)

문제 링크 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 - 3차원 배열의 그래프 탐색 문제 - 필드 초기화시 가로,세로,높이 변수가 혼란스러워 시간소요함 (그외에는 문제에서 요구하는 바와 같이 그대로 풀이하면 됨) - multisource bfs로 토마토(1)의 위치를 찾고, 위치값을 0으로 초기화(나머지는 -1) - 상하좌우위아래로 격자형 그래프 풀 듯이 이동하면서 위치값을 갱신하여 마지막에 최대값 찾으면 됨 ..

[BOJ 11725] 트리의 부모 찾기 (Java, 그래프 탐색)
알고리즘/그래프 탐색2023. 6. 9. 22:34[BOJ 11725] 트리의 부모 찾기 (Java, 그래프 탐색)

문제 링크 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 - BFS, DFS 로 문제 풀이 - 시간복잡도 : O(N^2) - 방문 배열과 같이 부모 배열 선언하고 연결된 노드의 부모 노드 정보를 갱신해주면 쉽게 풀리는 문제 제출 코드 BFS 로 할 경우 import java.util.*; import java.io.*; public class Main { static StringBuilder sb = new StringBuilder(); static int N; static List[] adj; st..

[BOJ 11403] 경로 찾기 (Java, 그래프 탐색)
알고리즘/그래프 탐색2023. 6. 9. 22:23[BOJ 11403] 경로 찾기 (Java, 그래프 탐색)

문제 링크 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 - 단방향 그래프 문제 예제 입력의 경우 아래와 같이 해석됨 예제 입력 1 3 0 1 0 0 0 1 1 0 0 예제 출력1 1 1 1 1 1 1 1 1 1 #정점(N)이 3개이고 간선이 존재한다는 뜻 1 -> 2 2 -> 3 3 -> 1 그래서 i = 1일때 1번 노드에서 방문 가능한 노드를 찾고 row 로 출력하면 되는 문제 i = 2일때 2번 노드에서 방문가능한 노드 찾아 row 출력 i = 3일때 3번 ..

[BOJ 2606] 바이러스 (Java, 그래프 탐색)
알고리즘/그래프 탐색2023. 6. 9. 21:54[BOJ 2606] 바이러스 (Java, 그래프 탐색)

문제 링크 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 - 양방향 그래프로 문제 풀이 - 방문 배열 사용하여 1번부터 연결된 정점에 대해 방문 처리 - 방문한 경우 바이러스 전파 된 것이므로 카운팅하여 결과 출력 제출 코드 - bfs, dfs 둘 다 정의 import java.util.*; import java.io.*; public class Main { static int N, LINE; static List[] adj; static b..

[BOJ 3184] 양 (Java, 그래프 탐색)
알고리즘/그래프 탐색2023. 6. 9. 21:48[BOJ 3184] 양 (Java, 그래프 탐색)

문제 링크 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이 - 전형적인 격자형 그래프 문제 - 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. - '.' (점)은 빈 필드를, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미 - 상하좌우로만 이동가능하며, 울타리는 이동 불가 - (조건) 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서..

[BOJ 2667] 단지번호붙이기 (Java, 그래프 탐색)
알고리즘/그래프 탐색2023. 6. 9. 21:40[BOJ 2667] 단지번호붙이기 (Java, 그래프 탐색)

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 - 전형적인 격자형 그래프 탐색 문제 - 방문배열을 사용하여, 방문하지 않고 배추가 심어져 있는 경우 상하좌우 방문처리하면서 그룹 카운팅 수행 - 가로, 세로 (5≤N≤25) 길이가 최대인 경우 시간복잡도는 O(N^2) = O(625) 이므로 Integer 처리 가능 제출 코드 - bfs, dfs 둘 다 정의 import java.util.*; import java.io.*; public cl..

반응형
image