본문 바로가기

Algorithm

 (252)
[백준] 7576 : 토마토 JAVA 풀이 익은 토마토의 주변을 점진적으로 탐색해야 하기 때문에 bfs를 사용했다. import java.io.*; import java.util.*; public class Main { static int[] dx = {0,0,-1,1}; static int[] dy = {1,-1,0,0}; static int[][] box; static int N; static int M; static Queue queue = new LinkedList(); static class Tomato{ int x; int y; Tomato(int x, int y){ this.x=x; this.y=y; } } public static void main(String[] args) throws IOException { BufferedRea..
[백준] 4963 : 섬의 개수 JAVA 풀이 땅인 부분에서 dfs나 bfs를 수행해서 하나의 섬을 다 탐색하고 그때마다 섬의 개수를 하나씩 증가시켜주면 되는 어렵지 않은 문제였다. import java.io.*; import java.util.*; public class Main { // 상하좌우, 대각선으로 이동하기 위한 좌표 static int[] dx = {0,0,-1,1,-1,-1,1,1}; static int[] dy = {1,-1,0,0,1,-1,1,-1}; // 지도와 해당 칸을 방문했는지 확인하기 위한 배열 static int[][] graph; static boolean[][] visit; // 섬의 개수 static int cnt = 0; static int W; static int H; public static void main..
[백준] 2667 : 단지번호 붙이기 JAVA 풀이 import java.io.*; import java.util.*; public class Main { // 상하좌우 이동을 위한 좌표배열 static int[] dx = {0,0,-1,1}; static int[] dy = {1,-1,0,0}; static int N; static int[][] graph; // 지도를 저장할 배열 static boolean[][] visit; // 방문했는지 체크하기 위한 배열 static int[] aparts = new int[25*25]; // 각 단지의 아파트 수 static int apartNum = 0; // 단지의 수 public static void main(String[] args) throws IOException{ BufferedReader br ..
[백준] 2331 : 반복수열 JAVA 풀이 그래프 카테고리에 있지만 그래프를 어떻게 적용해야 할지 모르겠어서 우선 어레이리스트로 풀어봤다. 1. A와 P를 입력받는다. 2. 순열을 저장할 어레이리스트를 생성한다. 3. D[1]이 되는 A를 리스트에 추가한다. 4. D[n-1]의 각 자리수를 P제곱한 합인 sum 구한다. 5-1. 4에서 구한 sum이 리스트에 이미 있다면 그 값의 인덱스를 출력하고 반복문을 종료한다. ( 반복수열을 제외한 수의 개수 = sum 앞에 있는 수의 개수. sum부터는 반복수열 ) 5-2. 4에서 구한 sum이 아직 리스트에 없는 값이라면 리스트에 추가한다. import java.io.*; import java.util.*; public class Main { public static void main(String[] a..
[백준] 10451 : 순열 사이클 JAVA 풀이 입력받는 방식을 제외하면 연결 요소의 개수를 세는 문제와 풀이가 같은 문제였다. import java.io.*; import java.util.*; public class Main { static int[][] graph; static boolean[] visit; static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 테스트케이스의 개수를 입력받음 int T = Integer.parseInt(br.readLine()); // 테스트케이스의 개수만큼 반복 for(int i=0;i
[백준] 11724 : 연결 요소의 개수 JAVA 풀이 우선 연결 요소가 무엇인지 몰라서 검색을 해봤다. 그래프 상에서 이어져 있는 모든 정점들이 있을 때 그것을 하나의 연결 요소라고 한다. 따라서 위 이미지에서는 3개의 연결 요소가 존재한다고 할 수 있다. 연결 요소의 개수를 구하는 방법은 간단하다. 아직 방문하지 않은 정점에 대해 BFS 또는 DFS를 수행하고 그때마다 연결 요소의 개수를 추가해주면 된다. 시작 정점에 대해 BFS 또는 DFS를 수행하면 인접 정점들을 모두 방문하게 되는데 이것은 하나의 연결 요소를 훑은 것과 같은 의미이기 때문이다. import java.io.*; import java.util.*; public class Main { static int[][] graph; static boolean[] visit; static int N..
[백준] 1260 : DFS와 BFS JAVA 풀이 인접행렬 방식으로 풀었다. import java.io.*; import java.util.*; public class Main { // 인접행렬 생성 static int[][] graph; // 방문했는지 확인하기 위한 행렬 static boolean[] visit; // 정점의 개수 static int N; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); // 정점의 개수 N = Integer.parseIn..
[백준] 1158 : 요세푸스 문제 JAVA 풀이 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Queue queue = new LinkedList(); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); // 1부터 N까지의 숫자를 큐에 넣음 for(int..

티스토리툴바