나이트의 이동(7562)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static int t, l, x, y, targetX, targetY, res;
static int[] dx = {-1, 1, 2, 2, 1, -1, -2, -2};
static int[] dy = {2, 2, 1, -1, -2, -2, -1, 1};
static boolean[][] visited;
static Deque<int[]> q = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine());
StringTokenizer st;
while (t-- > 0) {
l = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
// 나이트의 좌표
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
// 타겟 좌표
targetX = Integer.parseInt(st.nextToken());
targetY = Integer.parseInt(st.nextToken());
visited = new boolean[l][l];
res = bfs(x, y);
System.out.println(res);
}
}
static int bfs(int x, int y) {
visited[x][y] = true;
q = new ArrayDeque<>();
q.add(new int[]{x, y});
int cnt = 0;
while (!q.isEmpty()) {
int size = q.size();
// 현재 위치에서 갈 수 있는 모든방향 탐색
for (int i = 0; i < size; i++) {
int[] cur = q.pollFirst();
if (cur[0] == targetX && cur[1] == targetY) {
return cnt; // 타겟에 도달했으면 이동횟수 반환
}
for (int j = 0; j < 8; j++) {
int nx = cur[0] + dx[j];
int ny = cur[1] + dy[j];
if (nx < 0 || nx >= l || ny < 0 || ny >= l || visited[nx][ny]) continue;
visited[nx][ny] = true;
q.add(new int[]{nx, ny});
}
}
cnt++;
}
return cnt;
}
}
특정 거리의 도시 찾기(18352)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int node = Integer.parseInt(st.nextToken());
int edge = Integer.parseInt(st.nextToken());
int targetCnt = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
// 각 도시에서 도로가 연결되어 갈 수 있는 노드를 인접리스트로 저장
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= node; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < edge; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
graph.get(start).add(end); // 이동 가능한 도시
}
// 각 도시까지의 거리를 저장하는 배열
//아직 방문하지 않는 도시를 -1로 초기화
int[] distance = new int[node + 1];
Arrays.fill(distance, -1);
distance[x] = 0; // 출발 도시의 거리는 0으로 설정
Deque<Integer> q = new ArrayDeque<>();
q.add(x);
while (!q.isEmpty()) {
int cur = q.poll();
// 현재도시에서 연결된 다른 도시들 탐색
for (int next : graph.get(cur)) {
// 방문하지 않았을 경우 거리 증가시켜주고 다음 도시 큐에 추가
if (distance[next] == -1) {
distance[next] = distance[cur] + 1;
q.add(next);
}
}
}
boolean check = false; // 목표 거리에 해당하는 도시가 있는지 확인하기 위한 변수
for (int i = 1; i <= node; i++) {
if (distance[i] == targetCnt) {
System.out.println(i); // 목표 도시 출력
check = true;
}
}
// 목표거리에 해당하는 도시가 없으면 -1을 출력
if (!check) System.out.println(-1);
}
}
바이러스(2606)
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 {
static int n, connected;
static int[][] graph;
static boolean[] visited;
static Queue<Integer> q;
static StringTokenizer st;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
connected = Integer.parseInt(br.readLine());
graph = new int[n + 1][n + 1];
visited = new boolean[n + 1];
for (int i = 1; i <= connected; i++) {
st = new StringTokenizer(br.readLine());
int src = Integer.parseInt(st.nextToken());
int dst = Integer.parseInt(st.nextToken());
graph[src][dst] = 1;
graph[dst][src] = 1; //서로 연결되어 있음을 1로 표시
}
System.out.println(bfs(1));
}
private static int bfs(int num) {
q = new LinkedList<>();
visited[num] = true;
q.add(num);
int cnt = 0;
while(!q.isEmpty()) {
int current = q.poll();
for(int i = 1; i <= n; i++) {
if(graph[current][i] == 1 && !visited[i]) { // 연결되어있고, 방문하지 않았다면 감염시키기 위해 cnt 증가
cnt++;
q.add(i);
visited[i] = true;
}
}
}
return cnt;
}
}
Bucket Brigade(17198)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static char[][] farm = new char[10][10];
static boolean[][] visited = new boolean[10][10];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// B -> 불 난 헛간 R -> 바위 L -> 호수
for (int i = 0; i < 10; i++) {
farm[i] = br.readLine().toCharArray();
}
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
//if (farm[i][j] == 'R') visited[i][j] = true;
if (farm[i][j] == 'L') { // 호수 발견하면 해당 호수좌표에서 탐색 시작
bfs(i, j);
return;
}
}
}
}
static void bfs(int x, int y) {
Deque<int[]> q = new ArrayDeque<>();
visited[x][y] = true;
q.add(new int[]{x, y, 0}); // 좌표와 해당 좌표에 이동 횟수를 나타내는 배열
while (!q.isEmpty()) {
int[] cur = q.pollFirst();
int cnt = cur[2];
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
// 이동 좌표가 농장 밖 or 방문 한 곳 or 바위면 다음 순회로 넘어감
if (nx < 0 || nx >= 10 || ny < 0 || ny >= 10 || visited[nx][ny] || farm[nx][ny] == 'R') continue;
if (farm[nx][ny] == 'B') { // 헛간과 인접한 좌표에서 물을 끌수 있기때문에 다음 이동좌표가 헛간이면 바로 카운트 출력하고 탐색 종료
System.out.println(cnt);
return;
}
visited[nx][ny] = true;
q.add(new int[]{nx, ny, cnt + 1});
}
}
}
}
토마토(7569)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static int m, n, h, day;
static int[][][] box;
static boolean[][][] visited;
static Deque<Tomato> q = new ArrayDeque<>();
static int[] dx = {0, 0, -1, 1, 0, 0};
static int[] dy = {-1, 1, 0, 0, 0, 0};
static int[] dz = {0, 0, 0, 0, 1, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
box = new int[h][n][m];
visited = new boolean[h][n][m];
for (int i = 0; i < h; i++) {
for (int j = 0; j < n; j++) {
st = new StringTokenizer(br.readLine());
for (int k = 0; k < m; k++) {
box[i][j][k] = Integer.parseInt(st.nextToken());
// 익은 토마토 발견하면 해당좌표로부터 bfs탐색 시작
if (box[i][j][k] == 1) {
visited[i][j][k] = true;
q.add(new Tomato(i, j, k));
// 토마토가 들어있지 않는 칸은 방문 표시
} else if (box[i][j][k] == -1) {
visited[i][j][k] = true;
}
}
}
}
bfs(q);
System.out.println(day);
}
static void bfs(Deque<Tomato> q) {
while (!q.isEmpty()) {
Tomato now = q.pollFirst();
for (int i = 0; i < 6; i++) {
int nz = now.z + dz[i];
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if (nx < 0 || ny < 0 || nz < 0 || nx >= n || ny >= m || nz >= h || visited[nz][nx][ny]) continue;
visited[nz][nx][ny] = true;
if (box[nz][nx][ny] == 0) {
box[nz][nx][ny] = box[now.z][now.x][now.y] + 1; // 좌표 이동시 해당 토마토는 +하루
q.add(new Tomato(nz, nx, ny));
}
}
}
day = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
if (box[i][j][k] == 0) { // 익지 않은 토마토 하나라도 있으면 -1 출력
day = -1;
return;
}
day = Math.max(day, box[i][j][k]); // 익는데 가장 오래걸린 토마토를 출력하기 위함
}
}
}
day -= 1; // 처음익은 토마토는 1일차부터 시작하므로 날짜에서 1 빼줌
}
static class Tomato {
int z, x, y;
public Tomato(int z, int x, int y) {
this.z = z;
this.x = x;
this.y = y;
}
}
}