반응형 알고리즘 PS113 [백준] 11724번 - 연결 요소의 개수 (Java)(◎) https://www.acmicpc.net/problem/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 1. 연결 요소의 개수는 연결된 정점 그룹의 개수라고 생각하면 된다. 2. 방향성이 없는 그래프이므로 인접행렬로 받도록 하자. 1. 그룹화를 만드는 것이 관건이다. 메인함수에서 dfs를 호출할 때 for문을 돌려서 정점 1번부터 N번까지 돌면서 호출하자. 2. 방문배열 visited[]를 적극 활용해서 이미 방문한 정점은 스킵하자. 조.. 2022. 8. 31. [백준] 1012번 - 유기농 배추 (Java)(◎) https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1. 지렁이는 상/하/좌/우로만 연결된 배추로만 이동할 수 있으니, 상하좌우로 연결된 배추군집의 수를 구하면 된다. 2. 입력형식이 배추의 좌표이므로 이를 받아서 인접배열로 구성한다. 1. 상하좌우로 확장하면서 배추그룹을 만들면서 이동하면 된다. 2. dfs의 파라미터는 x, y 좌표를 넘겨준다. 3. 메인함수의 for문에서 1을 반견해서 dfs를 호출하면 새로운 그룹의 시작이므로 그때 count++를 해준다.. 2022. 8. 31. [백준] 2667번 - 단지번호붙이기 (Java)(◎) https://www.acmicpc.net/problem/2667 1. 정점은 집이다. 상하좌우로 탐색해서 1이면 다시 탐색을 계속한다. 2. 총 단지 수와 각 단지마다 집의 개수를 출력한다. 1. 메인함수에서 for문으로 dfs 함수를 호출한다. 2. 방문처리 된 곳이면 스킵하다가 새로운 1을 만나면 새로운 단지의 시작이다. 3. 방문배열을 방문처리할 때 count++를 하다가 새로운 단지를 만나면 초기화하자. 4. 단지 내 집의 수를 오름차순으로 정렬해서 출력해야 한다. 1. 입력함수에서 in.nextInt()로 받으면 안되고 한줄 단위로 문자열로 받은 다음 toCharArray()로 문자배열로 변환한 후에 ch - '0'을 해서 정수형으로 변환시켜서 배열에 저장해야 한다. 2. 출력함수에서 집의 수.. 2022. 8. 31. [백준] 2606번 - 바이러스 (Java)(◎) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 1. 컴퓨터 번호가 정점, 네트워크가 간선이다. 2. 바이러스가 감염되는 컴퓨터의 수는 간선을 통해 방문할 수 있는 정점의 수와 일치한다. 3. 1번 정점부터 dfs로 탐색을 해서 마지막에 카운팅한 수를 출력하면 된다. 4. 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력이니까 1번 컴퓨터는 카운팅하면 안된다. 1. 인접배렬로 입력값을 저장하고, 배열번호는 정점의 번호와 동일하게 1~.. 2022. 8. 31. [백준] 1260번 - DFS와 BFS (Java)(○) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. 무방향 그래프이다. 2. 방문할 정점이 여러개이면 작은 번호부터 방문하다. * DFS 1. 무방향 그래프를 표현하기 위해 vertex 배열을 사용한다. 2. DFS() 파라미터는 다음 방문할 정점 번호를 넘긴다. 3. DFS() 내부에서 for문으로 다음 방문 정점으로 확산한다. 4. 방문배열을 사용해서 방문할 정점은 스킵한다. 5. 간선이 아니면 (값이.. 2022. 8. 30. 이전 1 ··· 10 11 12 13 다음 반응형
