TEN BILLION

📌 N-Queen 문제란?N × N 크기의 체스판 위에 서로 공격하지 않도록 N개의 퀸(Queen)을 놓는 방법의 수를 구하는 문제입니다.퀸은 다음 위치에 있을 수 없습니다:같은 행같은 열같은 대각선🧩 문제 접근 방식N-Queen은 완전 탐색으로는 시간 초과가 발생하기 때문에 백트래킹(Backtracking) 을 활용합니다.백트래킹은 말 그대로, 불가능한 지점을 만나면 돌아가서 이전 상태로 되돌아가며 탐색하는 방식입니다.Java 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static int N, count; static int[] bo..

문제 설명권투 대회에 참가한 n명의 선수들이 1:1로 경기를 치렀습니다.모든 경기 결과는 모순 없이 주어지지만, 일부 결과가 누락되어 있어 모든 선수의 정확한 순위를 알 수는 없습니다.정확한 순위를 매길 수 있는 선수의 수를 구하라조건 정리선수 수 n: 1 ~ 100경기 결과 수: 1 ~ 4,500results[i] = [A, B] → A가 B를 이김결과는 항상 일관됨 (A가 B를 이기고 B가 C를 이기면 A는 반드시 C를 이김)선수 번호는 1부터 시작핵심1. 그래프 기반 추론이긴 선수: 1진 선수: -1모르는 관계: 02차원 배열(n+1 x n+1)로 승/패 관계를 저장합니다.2. 플로이드-워셜 알고리즘 적용간접적으로 추론 가능한 승패를 계산A가 B를 이기고 B가 C를 이기면 → A는 C를 이긴다3. ..

핵심안전 영역을 구하기 위해 BFS 탐색비의 높이 = k 라고 가정할 때, 높이 > k인 지역들로만 BFS 탐색높이 기준을 0 ~ maxHeight까지 변경하면서 최대 안전 영역 개수를 갱신실수 주의 포인트비가 아예 안 오는 경우, 즉 k = 0도 반드시 고려해야 합니다.이걸 누락하면 테스트케이스는 통과해도 실제 채점에서 오답 날 수 있어요. import java.io.*;import java.util.*;public class Main { static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static int[][] map; static boolean[][] visited; static int N; pub..

문제입력: 정점(N), 간선(V), 그리고 각 간선 정보출력: 주어진 그래프에서 연결 요소의 개수그래프는 무방향 그래프이며, 1번 노드부터 N번 노드까지 존재한다고 가정한다.접근 방법인접 행렬을 이용해 그래프를 저장한다.**방문 여부를 체크하는 배열(visited)**을 사용한다.모든 노드(1~N)에 대해 BFS를 수행하면서 연결 요소의 개수를 센다.코드 구현import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { ..

너비 우선 탐색(BFS, Breadth-First Search) 알고리즘을 사용하여 주어진 숫자 a에서 b로 가는 최소 횟수를 구하는 문제입니다.주어진 정수 a와 b에 대해, a에서 시작해 여러 가지 연산을 통해 b에 도달하려면 최소 몇 번의 연산이 필요한지를 구하세요. 가능한 연산은 다음과 같습니다:현재 숫자에서 1을 뺀다.현재 숫자에 1을 더한다.현재 숫자에 2를 곱한다.코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReade..

N × M 크기의 상자에 익은 토마토(1)와 익지 않은 토마토(0), 그리고 토마토가 들어있지 않은 칸(-1)이 있다. 익은 토마토는 하루가 지나면 상하좌우로 인접한 익지 않은 토마토를 익게 만든다. 모든 토마토가 익는 데 걸리는 최소 일수를 구하는 문제이다. 만약 모든 토마토를 익힐 수 없다면 -1을 출력해야 한다. 이 문제는 BFS(너비 우선 탐색) 을 활용하여 해결할 수 있다. BFS를 사용하면 여러 지점에서 동시에 탐색을 진행할 수 있으며, 최단 거리 계산에 유리하다.2. BFS 알고리즘을 활용한 해결 방법BFS 수행Queue를 사용하여 익은 토마토의 위치에서 시작하여 상하좌우로 탐색을 진행한다.각 날짜마다 익는 토마토를 Queue에 추가하고, 하루가 지날 때마다 days 값을 증가시킨다.queu..

그래프 탐색 방법입력을 받아 **배추밭(map)**을 2차원 배열로 생성방문 여부를 체크할 visited 배열을 선언배추(1)이고 방문하지 않은 곳을 발견하면 BFS 탐색 시작BFS 탐색을 통해 하나의 그룹을 완전히 방문 처리탐색이 끝날 때마다 count(흰지렁이 수) 증가BFS를 사용하면 연결된 모든 배추를 한 번에 방문할 수 있어, 효율적으로 그룹을 찾을 수 있습니다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class M..