Yong's Tech Story

https://school.programmers.co.kr/learn/courses/30/lessons/1844

import java.util.*;
    
class Solution {
    static int [][] dis; // 위치별 최단거리변수
    static boolean [][] visited; // 방문여부
    static int [] dx = {-1,1,0,0}; // 탐색할 x좌표
    static int [] dy = {0,0,-1,1}; // 탐색할 y좌표
    static int N;
    static int M;
    static int totalCnt=0;
    static int [][] arr; // 배열
    static int min = Integer.MAX_VALUE;
    public int solution(int[][] maps) {
        int answer = 0;
        N = maps.length;
        M = maps[0].length;
        arr = maps;
        
        dis = new int[N][M];
        visited = new boolean[N][M];
        
        bfs(0,0); // BFS 함수 동작(위치별 최단거리 계산)
        
        if(dis[N-1][M-1] == 0){
            answer = -1;
        }else{
            answer = dis[N-1][M-1]; // 마지막 도착 위치의 최단거리  
        }
        
        return answer;
    }
    public static void bfs(int x , int y){
        Queue<Point> queue = new LinkedList<>(); // 큐 선언
        
        visited[x][y] = true;
        dis[x][y] = 1;
        queue.offer(new Point(x,y)); // 좌표 x,y 큐에 입력
        
        // 큐가 없어질때까지 반복
        while(!queue.isEmpty()){
            Point cur = queue.poll(); // 현재 좌표x,y 추출
            for(int i=0; i<dx.length; i++){
                int nx = cur.x + dx[i]; // 탐색할 nx좌표
                int ny = cur.y + dy[i]; // 탐색할 ny좌표
                if(nx>=0 && nx < N && ny>=0 && ny < M && arr[nx][ny]==1 && visited[nx][ny]==false){
                    visited[nx][ny]=true;
                    dis[nx][ny]= dis[cur.x][cur.y] +1; // 해당 위치별 최단거리 계산 (이전 거리 + 1)
                    queue.offer(new Point(nx,ny)); // 큐에 nx,ny 좌표 입력
                }
            }
        }
    }
    // 좌표를 저장할 x,y 포인트 객체 선언
    public static class Point{
        int x;
        int y;
        Point(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
}

https://www.acmicpc.net/problem/1260

문제 풀이 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class baekjoon1260 {
	static List<ArrayList<Integer>> graph = new ArrayList<>(); // 인접리스트 그래프
	static boolean[] visited; // 방문 여부 배열
	static List<Integer> bfslist = new ArrayList<>(); // bfs 노드를 저장할 리스트
	static List<Integer> dfslist = new ArrayList<>(); // dfs 노드를 저장할 리스트

	public static void main(String[] args) throws IOException {
		// DFS와 BFS
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken()); // 정점의 개수
		int M = Integer.parseInt(st.nextToken()); // 간선의 개수
		int V = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점의 번호

		visited = new boolean[N + 1];

		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			// 양방향 그래프 세팅
			graph.get(a).add(b);
			graph.get(b).add(a);
		}

		// 그래프 오름차순 정렬
		for (int i = 1; i <= N; i++) {
			Collections.sort(graph.get(i));
		}

		bfs(V);

		visited = new boolean[N + 1];

		dfs(V);

		for (int i = 0; i < bfslist.size(); i++) {
			System.out.print(dfslist.get(i) + " ");
		}
		System.out.println();

		for (int i = 0; i < bfslist.size(); i++) {
			System.out.print(bfslist.get(i) + " ");
		}
	}

	private static void bfs(int num) {
		Queue<Integer> queue = new LinkedList<>();

		queue.offer(num);
		visited[num] = true;

		while (!queue.isEmpty()) {
			int cur = queue.poll();

			bfslist.add(cur);

			for (Integer next : graph.get(cur)) {
				if (visited[next] == false) {
					visited[next] = true;
					queue.offer(next);
				}
			}
		}
	}

	private static void dfs(int num) {
		visited[num] = true;
		dfslist.add(num);
		for (Integer next : graph.get(num)) {
			if (visited[next] == false) {
				dfs(next);
			}
		}
	}

}

주요 핵심 포인트

1. 위 문제는 BFS와 DFS의 기본을 알고 있는지를 묻는 문제로 개념적인 공부가 필요하다.

2. 출력값은 오름 차순을 기준으로 뽑아야 하기 때문에 그래프의 리스트를 오름차순으로 정렬하였다.

3. bfs 함수의 경우 큐를 사용하여 기본적인 bfs 함수를 갖추었고, 출력하고자 하는 값을 bfslist에 순서대로 저장하였다.

4. dfs 함수의 경우도 dfs의 기본 원리에 맞춰서 깊이 탐색을 진행하였다.

개선해야할 사항

: bfs와 dfs의 값을 출력하기 위하여 리스트를 선언하였으나, 리스트가 아니라 출력을 사용하여 푸는 방법도 있을 듯하다. 필자는 main에서 값을 출력하는 것을 선호하여 리스트로 만들었지만, 함수에서 print() 처리를 하는 방법도 생각해보아야 겠다.

문제 풀이 (JAVA)

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

public class part7_8 {
	static int K; // 송아지 위치
	static int level; // 레벨(점프횟수)

	public static void main(String[] args) {
		// 송아지 찾기1(BFS)
		Scanner input = new Scanner(System.in);

		int N = input.nextInt(); // 철수의 위치
		K = input.nextInt(); // 송아지의 위치
		bfs(N);
	}

	private static void bfs(int N) {
		Queue<Integer> queue = new LinkedList<>();
		int min = Integer.MAX_VALUE; // 최소 거리 변수
		queue.offer(N); // 철수의 위치 N 삽입
		while (queue.peek() != K) { // 철수의 위치가 송아지의 위치가 아닐동안 반복
			int cur = queue.peek(); // 철수의 현재 위치 변수
			min = Integer.MAX_VALUE; // 최소 거리 변수 초기화
			queue.offer(cur + 1); // 점프 +1
			queue.offer(cur - 1); // 점프 -1
			queue.offer(cur + 5); // 점프 +5
			int len = queue.size(); // 큐의 경우 사이즈
			for (int i = 0; i < len; i++) {
				int num = Math.abs(K - queue.peek()); // 최소거리 변수(송아지의 위치-철수의 점프 후 위치)
				if (min > num) { // 최소 거리를 저장
					min = num;
				}
				queue.offer(queue.poll()); // 큐의 변수를 한바퀴 돌린다.
			}
			for (int i = 0; i < len; i++) {
				// 지정한 최소거리가 아니라면 큐에서 제거
				if (min != Math.abs(K - queue.peek())) {
					queue.poll();
				} else {
					// 지정한 최소거리라면 큐에 다시 넣는다.
					queue.offer(queue.poll());
				}
			}
			// 한번 다 돌았을시 점프후 최소거리 변수만 큐에 남음.
			level++; // 횟수 카운트 증가
		}
		System.out.print(level);
	}
}

주요 핵심 포인트

1.  점프 한번시 +1, -1 , +5 만큼 갈 수 있으므로 경우의수는 3가지가 된다. 그 중 목표값 K와 가장 가까운 값을 K- (이동한값) 중 가장 크기가 적은 값이 송아지의 위치와 가까워지므로 최소값을 Math.abs()로  구하였다.

2. 철수의 첫번째 값 N을 큐에 넣고, +1,-1,+5의 증가되는 값들을 뒤이어 차례로 넣는다.

ex) 철수의 처음 위치 = 5 라면 큐 (5 <- 6 <- 4 <- 10) , 송아지의 위치 = 14

3. 송아지의 위치와 큐에 적재되어 있는 값들 중 (송아지의 위치- 적재된 큐) 를 하여 가장 차이가 적은 값이 최적의 이동값으로 큐를 앞부터 비교하여 한번씩 재적재하여 최소값을 구한다.

ex) 14 - 5 = 9 , 14 - 6 = 8 , 14 - 4 =10 , 14 - 10 = 4   => 최소값 = 4

4.  재적재된 큐와 최소값이 일치하는지 다시 비교하여 일치하지 않는 경우 제거하고, 일치하는 경우 큐에 재적재하였다.

ex) 큐( 5 <- 6 <- 4 <-10) -> (6 <- 4 <- 10) -> (4<- 10) -> (10)

5. 최종적으로 하나의 값이 남으며 해당 값이 다음 점프 값이 되며, 점프횟수를 가리키는 level을 1 증가시킨다.

6. 1~5를 반복하여 점프한 최종 값이 송아지의 위치와 같아진다면 반복을 종료한다.

개선해야할 사항

1.  위처럼 생각하여 풀이하였을 때, 시간 효율성은 괜찮게 나왔다. 강의와 비교하였을때 강의에서의 시간 효율성보다 내가 풀었던 시간 효율성이 조금 더 괜찮지 않나 싶다. K의 값이 크더라도 5씩 증가하기 때문에 K/5 * 2n번을 반복하므로 모든 수를 비교하지는 않아 시간 효율성이 좋게 나온듯 하다. bfs는 최적의 경로 문제를 풀기에 적절한 문제임을 인지하자.