[스터디] Java 알고리즘 2문제 (25.02.21)

1. 백준 1697 - 숨바꼭질

• BFS로 최단 경로 찾기
• N(0 ≤ N ≤ 100,000), K(0 ≤ K ≤ 100,000) 범위 내에서 조건 처리
• 순간이동, 전진, 후진의 3가지 조건

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();

		boolean[] visited = new boolean[100001];
		Queue<int[]> q = new LinkedList<>();
		int time = 0;

		q.offer(new int[] { N, time });
		visited[N] = true;

		while (!q.isEmpty()) {
			int[] arr = q.poll();
			int cur = arr[0], curTime = arr[1];
			if (cur == K) {
				System.out.print(curTime);
				break;
			}

			if (cur * 2 <= 100000 && !visited[cur * 2]) {
				q.offer(new int[] { cur * 2, curTime + 1 });
				visited[cur * 2] = true;
			}
			if (cur + 1 <= 100000 && !visited[cur + 1]) {
				q.offer(new int[] { cur + 1, curTime + 1 });
				visited[cur + 1] = true;
			}
			if (cur - 1 >= 0 && !visited[cur - 1]) {
				q.offer(new int[] { cur - 1, curTime + 1 });
				visited[cur - 1] = true;
			}
		}

		sc.close();
	}

}

2. SWEA 2805 D3 - 농작물 수확하기

import java.util.Scanner;

public class Solution {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		

		for (int i = 0; i < T; i++) {
			int N = sc.nextInt();
			int[][] farm = new int[N][N];
			int sum = 0;

			sc.nextLine();
			for (int j = 0; j < N; j++) {
				String str = sc.nextLine();
				for (int a = 0; a < N; a++) {
					farm[j][a] = str.charAt(a) - '0';
					sum += farm[j][a]; // 전체 합 구하기
				}
			}

			// 전체 - 왼쪽 위 하얀 부분 삼각형 
			for (int x = 0; x < N / 2; x++) {
				for (int y = 0; y < N / 2 - x; y++) {
					sum -= farm[x][y];
				}
			}

			// 전체 - 오른쪽 위 하얀 부분 삼각형 
			for (int x = 0; x < N / 2; x++) {
				for (int y = N / 2 + x + 1; y < N; y++) {
					sum -= farm[x][y];
				}
			}

			// 전체 - 왼쪽 아래 하얀 부분 삼각형 
			for (int x = N / 2 + 1; x < N; x++) {
				for (int y = 0; y < x - N / 2; y++) {
					sum -= farm[x][y];
				}
			}

			// 전체 - 오른쪽 아래 하얀 부분 삼각형 
			for (int x = N / 2 + 1; x < N; x++) {
				for (int y = N - x + N / 2; y < N; y++) {
					sum -= farm[x][y];
				}
			}

			sb.append("#").append(i+1).append(" ").append(sum).append("\n");

		}
		System.out.println(sb);
		sc.close();

	}

}