본문 바로가기

분류 전체보기

 (268)
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 그래프에 간선을 직접 넣지않고 [N+1][N+1] 그래프를 만들어 각 노드의 관계를 입력했다 for(int i=1; i 2 1 0 0 0 1 0 줄을 탐색하는것 첫번째 for문에서 1(시작)>2>5 를 탐색하고 res를 증가시키는것 두번째는 3(시작)>4>6 을 탐색후 res증가후 종료 (visited가 다 true) import java.util.LinkedList; import java.util.Q..
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 6 8 -> 정점의 수와 간선 1 2 2 5 5 1 3 4 4 6 5 4 2 4 2 3 그래프에 위 노드를 생성하고 [{1,2},{2,5}...] 방문했는지 확인하는 visited[간선] 를 만들었다 visited[M][M] 으로 만들지 않은 이유는 어자피 [0][0] 과 [0][1] 은 이어져있으니 같이 방문하기 때문에 for문을 돌면서 각 간선의 방문여부를 확인한다. 만약 방문안했다면 bfs에서 그..
2468-안전영역 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 쉬운문제인데 몇 번 틀렸다.. 알고보니 비가 오지 않는 경우도 계산해야 한다고 한다. 그래서 비의 범위를 0부터 100까지 계산한다. import java.util.*; public class B2468 { static int N; static int[][] Board; static boolean[][] visited; static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}}; static class Node{ int row,col; Node..
2667-단지번호붙이기 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 1. move에서 방문하지 않은 단지를 찾는 후 bfs로 좌표를 넘긴다 2. bfs에서 해당 단지를 모두 탐색 후 단지 너비 반환 3. 반환한 너비를 ArrayList에 저장 후 다음단지를 찾는다. 반복 이전에 푼 문제와 비슷해서 쉽게 풀었는것 같다 package com.exam; import java.util.*; public class B2667 { static int N; static int[][] Board; static int[][] D = {{-1,0}..
2331-반복수열 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 재귀함수를 사용하여 DFS를 구현하였다 1. dfs에서 숫자를 받아서 배열 저장 후 다음 순서 숫자를 구한다 2. 만약 현재 숫자와 다음숫자가 (같은순서로) 이미 배열에 존재하는 숫자의 순서라면 3. dfs를 빠져나간다 package com.exam; import java.util.ArrayList; import java.util.Scanner; public class B2331 { static int A,P; static ArrayList sumArr = new ArrayList(); static boolean finish; static void dfs(int a){ s..
10451-순열사이클 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 처음에는 입력을 두 개씩 받아서 [(1,3),(2,2)....] 식으로 풀다가 index랑 비교하여 푸는 방법을 찾아서 새로 풀어보았다 import java.util.Scanner; public class B10451 { static int[] intArr; static boolean[] visited; static int dfs(int j){ if(j == intArr[j] || visit..
2178-미로탐색 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class B2178 { static int N,M; static int[][] Board; static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}}; //상 하 좌 우 static boolean[][] visited; static class Node{ int row, col, count; Node(int r, in..
1620-DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net package com.exam; import java.util.*; public class B1260 { static int N,L,S; static int[][] Board; static boolean[] visited; static ArrayList compare; public static void bfs(){ Queue queue = new LinkedList(); visited = new boolean[N]; visi..

티스토리툴바