문제 링크 연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net ❗ 풀이 방법 문제가 복잡한 만큼 로직을 나눠서 생각한 뒤, 구현해주는 것이 좋다. 문제를 읽어보면 다음의 세가지 로직이 필요한 것을 깨달을 수 있다. 벽을 세워보는 로직 바이러스를 퍼트리는 로직 안전영역의 갯수를 세는 로직 이렇게 정리가 되었다면, 다음은 위 세가지 로직을 어떻게 구현할 지 생각해보아야 한다. 벽을 세워보는 로직 모든 조합수를 따져보아야 하니 백트래킹으로 벽을 세워보고 허물어보고 하는식으로 하는것이 적절하지 않을까? 따라서 벽을 3개까지 세..

문제 링크 순열 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static int count; static String answer; static char[] arr; static boolean[] visited; static boolean flag; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { St..

문제 링크 로또 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static int k; static int[] arr; static boolean[] visited; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true) { k ..

문제 링크 N과 M 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static StringBuilder sb = new StringBuilder(); static int n; static int m; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); solution(); Sy..

문제 링크 N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ❗ 풀이 방법 대표적인 백트래킹 문제이다. 처음에 퀸의 위치를 1차원 배열에 기록하면서 백트래킹하는 아이디어를 떠올리지 못하여 2차원 배열의 체스판을 만든 뒤 모든 칸에 대하여 퀸을 놓아본 다음 퀸을 놓은 위치와 공격할 수 있는 위치를 방문처리하고, 카운팅한 다음 방문처리를 풀어주는 굉장히 수고스러운 로직을 구현하였는데 다른 사람의 풀이를 보고 해당 아이디어를 베껴와서 다시 풀었더니 쉽게 풀렸다.. private static int[] arr; priv..

문제 링크 토마토 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static class Position { int x; int y; Position(int x, int y) { this.x = x; this.y = y; } } // BFS 탐색을 위한 queue 선언 static Queue queue = new LinkedList(); // 방향벡터 정의 static int[] dx = {1, 0, -1, 0}..

문제 링크 유기농 배추 풀이 코드 import java.util.*; public class Main { // 위치클래스 선언 static class Position { int x; int y; Position(int x,int y) { this.x = x; this.y = y; } } // 방향벡터 정의. static int[] dx = {1, 0, -1, 0}; static int[] dy = {0, 1, 0, -1}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); StringBuilder sb = new StringBuilder(); while(t > 0) { int ..

문제 링크 섬의 개수 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static class Position { int x; int y; Position(int x, int y) { this.x = x; this.y = y; } } // BFS 탐색을 위한 Queue 정의. static Queue queue = new LinkedList(); // 방향벡터 정의(상, 하, 좌, 우, 대각선) static int[] dx =..

문제 링크 바이러스 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 풀이 코드(DFS) import java.util.*; public class Main { static int n; static int m; static int[][] graph; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); //정점의 개수 m = sc.nextInt(); //간선의 개수 graph = new int[n+1..

문제 링크 미로 탐색 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static class Position { int x; int y; Position(int x, int y) { this.x = x; this.y = y; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();; int m = sc.nextInt();; int[]..

문제 링크 DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static int n; static int m; static int[][] graph; static boolean[] visited; /** * 입,출력 */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nex..

문제 링크 한수 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 풀이코드 import java.util.*; public class Main { static int answer; /** * 입,출력 */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); print(solution(n)); } private static int solution(int n) { int answer = 0; ..