2월 29, 2024

[Java/Spring] Custom Annotation 만드는 방법, @Retention, @Target 등 meta annotation

1. Java Annotation


Java에서는 기본적으로 제공되는 Built-in annotatoin들이 있다. 우리가 스프링, 자바 공부를 하면서 자주 보았던 @Override나 @SuppressWarnings 와 같은 annotation이 대표적으로 Built-in annotation들이다. 하지만 스프링 개발을 하다 보면 Customized 된 annotation을 만들어서 일관성 있게 우리가 원하는 방식으로 개발하고 싶어질 때가 있다. 그런 경우를 위하여 오늘은 Custom annotation을 만드는 방법에 대하여 알아보겠다. 


2. Custom Annotation 생성하기 


만약 우리가 @Name이라는 annotatotion을 생성하여 DVo와 같은 java 파일에 각 필드마다 @Name annotation을 붙여주고 싶다고 해보자. 

그러면 아래와 같이 작성하면 된다. 

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.FIELD, ElementType.METHOD, ElementType.TYPE})
public @interface Name{
   String value();
}

annotation은 @interface 라고 해서 만들어주면 되고 
그 이외에 여러 Meta annotation을 붙여주면 되는 것이다.

예를 들어 

@Retention(RetentionPolicy.RUNTIME)

의 경우 컴파일 이후 runtime 까지도 계속 참조가 되게끔 설정한 것이다.

@Target annotation 뒤에는 해당 annotation이 사용되는 위치를 결정해준다. 

여기서 자주 사용되는 것이 ElementType.FIELD, ElementType.METHOD, ElementType.TYPE인데 
FIELD는 멤버 변수 선언, METHOD는 메소드, TYPE은 타입 선언 시 활용된다. 

해당 형태에 우리가 정의한 annotation을 사용할 수 있는 것이라고 생각하면 된다.

예를 들어 ElementType.METHOD를 정의하지 않으면 우리는 해당 애노테이션을 메소드에는 사용할 수 없다. 

따라서 굳이 필요하지 않다면 명시해주지 않아도 된다는 뜻이다. 


위와 같이 만들었다면 우리는 

Dvo와 같이 각 멤버 변수 위에 @Name을 정의하여 우리가 부르고 싶은 이름을 보기 좋게 나타낼 수 있다. 

@Name("한국나이") 
private int age; 

이런 식으로 각 멤버 변수가 무엇을 의미하는지 적어줄 수 있다. 

마찬가지로 ElementType.METHOD를 통해 메소드에도 적용 가능하도록 설정을 하였으므로

@Name("한국나이 Setter Method")
public void setAge(int age) {
    this.age = age; 
}

이런 식으로 이름을 적어줄 수 있다. 

꼭 위와 같은 @Name이 아니더라도 적절한 annotation을 생성하여 효과적으로 Java 프로그램을 관리해보자. 

2월 29, 2024

[백준] 16947번 서울지하철문제 그래프를 활용하여 풀기

1. 문제

1) 링크

www.acmicpc.net/problem/16947

2) 문제

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.

3) 입력

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.

4) 출력

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

 

더 자세한 문제의 제한사항은 위의 링크에 들어가서 확인해보자.


2. 풀이


이 문제는 싸이클을 찾는

 

https://www.programmingstory.com/2024/02/16929-two-dots-dfs.html


위의 포스팅에서 다룬 내용과 비슷하지만 다른 점이 있다. 



만약 위와 같은 그래프가 있다면1-2-3-4-5-6 이런식으로 돈다고 생각했을 때 싸이클이 1개 만들어지지만 5번과 6번 노드는 싸이클의 일부가 아니다. 따라서 지하철 문제는 전체를 돈 후 싸이클이 완성되더라도 해당 노드가 싸이클의 일부인지 아닌지를 판단하는 과정이 하나 더 필요하다. 

 


먼저 이 문제의 find함수의 원형을 살펴보자

find(int prev, int x)라는 함수는 싸이클 찾는 방법을 활용하기 위해 전의 노드와 현재 노드의 값을 매개변수로 받는 함수이다. 이 문제의 return 값을 정해보았다. (이 숫자를 무엇으로 정하느냐는 본인의 마음이다)

  • -2: 싸이클은 찾았으나, 해당 노드가 싸이클에 포함되지 않음. 위의 그림에서 5번과 6번 같은 느낌
  • -1: 싸이클을 찾지 못했다. (전체를 다 돈 후에도 return이 되어 있지 않으면 return -1을 해주는 것)
  • 0~n-1: 싸이클을 찾았다. 이 경우, 싸이클의 맨 처음 index를 return해준다. (처음 인덱스라는 것은 예를 들어 1 노드에서 시작하여 다시 1로 돌아왔을 경우 시작 인덱스가 1이 된다.)

find 함수의 코드는 아래와 같다. 

 public static int find(int prev, int x){
        if (check[x]==1){   //예전에 방문한 노드에 다시 방문 (싸이클을 찾음)
            return x;
        }
        check[x]=1;
        for(int y: a[x]){ //인접리스트 사용
            if (y==prev){ //이전 노드와 같으면 continue
                continue;
            }
            int num=find(x, y);
            if (num==-2) return -2;  //싸이클을 찾지 못함
            if (num>=0){
                check[x]=2; //싸이클의 일부라는 뜻
                if (x==num){return -2;}  //시작노드와 같으면 이 이후로는 싸이클이 아니므로 -2 리턴
                else return num;
            }
        }
        return -1; 
    }

 

여기서 check 배열이 나오는데 check 배열에는 그냥 방문한 노드면 1을 저장, 방문했는데 싸이클 (순환선)의 일부이면 2를 저장하는 식으로 구했다. 


그러면 이제 각 노드에서 순환선 사이의 거리를 구해야 한다. 해당 노드가 싸이클의 일부면 check에다가 2를 저장했으므로, check의 값이 2 이면 거리는 0이다. 

맨 처음 queue에는 순환선인 node들만 추가를 하고 이후,

    while (!q.isEmpty()) {
            int x = q.remove();
            for (int y : a[x]) {
                if (distant[y] == -1) {
                    q.add(y);
                    distant[y] = distant[x]+1;
                }
            }
        }

위와 같이 코드를 구성해주면 된다. 인접한 것은 그 전 노드의 거리에다가 1을 더한 것이기 때문이다. 


3. 코드

위 과정을 거쳐 전체 코드는

import java.util.*;

public class Main{
    public static ArrayList<Integer>[] a;
    public static int[] check;
    public static int[] distant;
    public static int find(int prev, int x){
        if (check[x]==1){
            return x;
        }
        check[x]=1;
        for(int y: a[x]){
            if (y==prev){
                continue;
            }
            int num=find(x, y);
            if (num==-2) return -2;
            if (num>=0){
                check[x]=2;
                if (x==num){return -2;}
                else return num;
            }
        }
        return -1; 
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        
        a=(ArrayList<Integer>[])new ArrayList[n];
        check=new int[n];
        distant=new int[n];
        for(int i=0; i<n; i++){
            a[i]=new ArrayList<Integer>();
        }
         Queue<Integer> q = new LinkedList<>();
        for(int i=0; i<n; i++){
            int from=sc.nextInt()-1;
            int to=sc.nextInt()-1;
            a[from].add(to);
            a[to].add(from);
        }
        find(-1, 0);
        
        for (int i=0; i<n; i++) {
            if (check[i] == 2) {
                distant[i] = 0;
                q.add(i);
            } else {
                distant[i] = -1;
            }
        }
        while (!q.isEmpty()) {
            int x = q.remove();
            for (int y : a[x]) {
                if (distant[y] == -1) {
                    q.add(y);
                    distant[y] = distant[x]+1;
                }
            }
        }
        for (int i=0; i<n; i++) {
            System.out.print(distant[i] + " ");
        }
        System.out.println();
    }
}

위와 같이 작성할 수 있다. 



2월 29, 2024

[백준] 7576번 토마토문제 BFS로 풀기

1. 문제

1) 링크

www.acmicpc.net/problem/7576

2) 문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

3) 입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

4) 출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

더 자세한 문제사항은 위의 링크에 들어가서 확인해보자


2.풀이

https://www.programmingstory.com/2024/02/2178-bfs-dfs.html

우선 이 문제는 위의 문제와 굉장히 유사하다. 이 문제 또한 그래프 문제인데 BFS로밖에 풀수 없는 문제이다. 그 이유는 위의 포스팅에서 설명해놓았으니 들어가서 확인해보자.

 

이 문제가 위와 다른 한 가지 점은 시작점이 주어져있지 않다는 것이다. 위의 문제는 점 (1,1)에서 시작하는 것이기 때문에 queue에 시작점을 먼저 넣고 시작을 하면 되었는데 이 문제는 어디서 시작하는지 주어져 있지 않기 때문에 다르다. 따라서 문제에서 익은 토마토를 입력을 받으면 해당 칸을 queue에다가 넣어주는 과정이 필요하다. 전체 모든 칸의 distance를 우선 -1로 초기화해준 후 익은 토마토의 distance는 0으로 바꾸어서 시작하면 된다.

 

여기서는 또한 전의 문제처럼 check 배열을 사용하지 않아도 푸는 것이 가능한데 이유는 distance가 -1이 아니라는 이야기는 이미 계산이 되었다는 이야기와 같기 때문이다. 

 

따라서 이 문제는 입력을 받을 때 queue에 넣어야 한다는 것을 처리해주어야 한다. 해당 부분의 코드는 아래와 같다.

 Queue<Pair> q=new LinkedList<>();
        for(int i=0; i<n; i++){
            
            for(int j=0; j<m; j++){
                distance[i][j]=-1;
                a[i][j]=sc.nextInt();
                if (a[i][j]==1){
                    q.add(new Pair(i,j));
                    distance[i][j]=0;
                }
            }
        }

여기서 이미 익은 토마토는 queue에다가 넣어주었고 distance도 0으로 처리해주었다.  (이 토마토들이 시작점이 되서 위,아래, 좌, 우를 검사하는 것이다)


 while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if (a[nx][ny] == 0 && distance[nx][ny] == -1) {
                        q.add(new Pair(nx, ny));
                        distance[nx][ny] = distance[x][y] + 1;
                    }
                }
            }
        }

위의 코드는 queue를 처리해주는 부분이다. 이것 또한 인접한 것들을 살펴보면서 distance를 하나씩 증가시켜준다.


3. 코드

최종코드를 살펴보면

import java.util.*;
class Pair{
    int x, y;
    Pair(int x, int y){
        this.x=x;
        this.y=y;
    }
}
public class Main{
    public static int [][]a;

    public static int distance[][];
    public static int []dx={0,0,1,-1};
    public static int []dy={1,-1,0,0};
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        a=new int [n][m];
        distance=new int [n][m];
         Queue<Pair> q=new LinkedList<>();
        for(int i=0; i<n; i++){
            
            for(int j=0; j<m; j++){
                distance[i][j]=-1;
                a[i][j]=sc.nextInt();
                if (a[i][j]==1){
                    q.add(new Pair(i,j));
                    distance[i][j]=0;
                }
            }
        }
        
       while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if (a[nx][ny] == 0 && distance[nx][ny] == -1) {
                        q.add(new Pair(nx, ny));
                        distance[nx][ny] = distance[x][y] + 1;
                    }
                }
            }
        }
        int ans=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if (distance[i][j]>ans){
                    ans=distance[i][j];
                }
            }
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if (a[i][j]==0 && distance[i][j]==-1){
                    ans=-1;
                }
            }
        }
        System.out.println(ans);
        
      
    }
}

위와 같이 쓸 수 있다. 


2월 29, 2024

[백준] 2178번 미로탐색 BFS 탐색으로 풀기 (DFS로는 풀 수 없는 이유?)

1. 문제

1) 링크

www.acmicpc.net/problem/2178

2) 문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

3) 입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

4) 출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

더 자세한 문제의 사항을 보려면 위의 링크로 들어가보자.


2. 풀이

대부분의 그래프 문제는 BFS, DFS 두 방법으로 모두 가능하다. 하지만 이 문제는 DFS로는 풀 수 없고, BFS로밖에 푸 수 없다는 점에서 특이한 문제이다. 

이는 왜냐하면 DFS의 경우 가능한 경우를 찾으면 되는 것이지 가장 빠른 길을 구하는 것이 아니기 때문이다. BFS의 경우에는 매 단계마다 가능한 경우를 탐색하기 때문에 (N,M)에 도달할 때까지 단계별로 시도해볼 수 있는 것이기 때문이다. 

 

따라서 이 문제는 BFS로 풀면서 모든 칸의 거리를 저장해 놓을 배열이 필요하다. 


이 문제의 준비 배열

1. int [][] distance=new int[n][m];
   //각 칸마다 거리를 저장해 놓을 배열이 필요함
2. boolean [][]check=new boolean [n][m];
  // BFS를 하면서 이미 사용된 칸인지 체크. 사용되었으면 해당 칸을 true로 바꾸어놓음
3. Queue<Pair> queue=new LinkedList<>();
  //BFS를 하기 위해 필요한 queue. 

4. class Pair
  //x행, y열을 기록하기 위해서 Pair라는 객체가 필요함. 이를 위해 class를 만들었음

 

각 칸마다 이 문제는 위, 아래, 좌, 우를 살펴보면서 해당칸이 사용이 되지 않았고 문제에서 입력받은 해당 칸의 숫자가 1이면 해당 칸의 거리를 1 증가하여 distance배열에 저장한다. 

 

이것을 코드화시켜서 BFS 부분만 살펴보자. 

 Queue<Pair> queue=new LinkedList<>();
        queue.add(new Pair(0,0));
        check[0][0]=true;
        distance[0][0]=1;
        while(!queue.isEmpty()){
            Pair p=queue.remove();
            int x=p.x;
            int y=p.y;
            for(int i=0; i<4; i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if (nx>=0 &&ny>=0 &&nx<n &&ny<n){
                    if (check[nx][ny]==false && a[nx][ny]==1){
                        queue.add(new Pair(nx, ny));
                        distance[nx][ny]=distance[x][y]+1;
                        check[nx][ny]=true;
                    }
                }
            }
        }

처음에 (1,1) 자리의 Pair를 queue에다가 넣은 뒤 시작해준다. 여기서는 배열이기 때문에 [0][0] 이 (1,1)을 의미한다. 

 

이 문제도 저번에 다루었던,

https://www.programmingstory.com/2024/02/2667.html

위의 문제와 유사하나 이 문제는 BFS로밖에 풀 수 없다는 것이 특징이다. 만약 DFS로 푸는 것이 궁금하다면 위의 포스팅에서는 DFS로 푼 코드를 첨부했으니 살펴보자.


3. 코드

최종적으로 전체 코드를 살펴보면 아래와 같다. 

import java.util.*;
class Pair{
    int x,y;
    Pair(int x, int y){
        this.x=x;
        this.y=y;
    }
}
public class Main{
    public static final int dx[]={0,0,1,-1};
    public static final int dy[]={1,-1,0,0};
    public static void main (String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int a[][]=new int[n][m];
        for(int i=0; i<n; i++){
            String s=sc.next();
            for(int j=0; j<m; j++){
              a[i][j]=s.charAt(j)-'0';
            }
        }
        int [][] distance=new int[n][m];
        boolean [][]check=new boolean [n][m];
        Queue<Pair> queue=new LinkedList<>();
        queue.add(new Pair(0,0));
        check[0][0]=true;
        distance[0][0]=1;
        while(!queue.isEmpty()){
            Pair p=queue.remove();
            int x=p.x;
            int y=p.y;
            for(int i=0; i<4; i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if (nx>=0 &&ny>=0 &&nx<n &&ny<m){
                    if (check[nx][ny]==false && a[nx][ny]==1){
                        queue.add(new Pair(nx, ny));
                        distance[nx][ny]=distance[x][y]+1;
                        check[nx][ny]=true;
                    }
                }
            }
        }
        System.out.println(distance[n-1][m-1]);
    }
    
}

2월 29, 2024

[백준] 4963번 섬의 개수 BFS/DFS 사용해서 풀기

1. 문제

1) 링크

www.acmicpc.net/problem/4963 

2) 문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

3) 입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

4) 출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

문제의 세부 조건들을 확인하려면 위의 링크에 들어가서 확인해보자.

 


2. 풀이

참고로 이 문제는

https://www.programmingstory.com/2024/02/2667.html

위의 문제와 굉장히 유사하니 위의 문제를 먼저 공부하고 오는 것을 추천한다.

다른 점은 위 문제에서는 위, 아래, 왼쪽, 오른쪽 네 가지 방향으로만 움직일 수 있었는데 이 섬 문제의 경우, 대각선으로 움직이는 것도 포함하는 것이다. 

 

따라서, 

배열 부분이

public static final int[] dx={1,-1,0,0,1,-1,-1,1};
public static final int[] dy={0,0,1,-1,1,-1,1,-1 };

위와 같이 추가되게 된다. 

 

이 문제도 DFS를 활용해서 구현을 해 보았는데 DFS 함수의 코드만 우선 보자면,

 public static void dfs(int x, int y, int cnt){
        group[x][y]=cnt;
        for(int i=0; i<8; i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if (nx>=0 && ny>=0 && nx<n&& ny<m){
                if (a[nx][ny]==1&&group[nx][ny]==0){
                    dfs(nx, ny, cnt);
                }
            }
        }
    }

위와 같이 쓸 수 있다. 대각선까지 이동할 수 있기 때문에 총 이동할 수 있는 방법이 8개나 된다. 따라서 이번에는 for문을 8번 돌았다.


나머지 알고리즘은 모두 위의 단지번호붙이기 (백준 2667번)과 유사하니 전체 코드만 첨부해보겠다. 

import java.util.*;

public class Main{
    public static int [][]a;
    public static int [][]group;
    public static int n;
    public static int m;
    public static final int[] dx={1,-1,0,0,1,-1,-1,1};
    public static final int[] dy={0,0,1,-1,1,-1,1,-1 };
    public static void dfs(int x, int y, int cnt){
        group[x][y]=cnt;
        for(int i=0; i<8; i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if (nx>=0 && ny>=0 && nx<n&& ny<m){
                if (a[nx][ny]==1&&group[nx][ny]==0){
                    dfs(nx, ny, cnt);
                }
            }
        }
    }
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        while(true){
            m=sc.nextInt();
          n=sc.nextInt();
            if (n==0 && m==0){
                break;
            }
            a=new int [n][m];
            group=new int [n][m];
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    a[i][j]=sc.nextInt();
                }
            }
            int cnt=0;
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if (a[i][j]==1 && group[i][j]==0){
                        dfs(i,j, ++cnt);
                    }
                }
            }
            System.out.println(cnt);
        }
      
        
    }
}

2월 29, 2024

[백준] 1991번 트리순회 출력문제 코드

1. 문제

1) 링크

www.acmicpc.net/problem/1991

2) 문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

  • 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
  • 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
  • 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

3) 입력

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.

4) 출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

더 자세한 문제의 제한을 보기 위해서는 위의 백준 링크에 들어가 보자


2. 트리 자료 구조

이 문제는 트리의 구조와 트리의 순화방법을 알지 못한다면 절대로 풀 수 없는 문제이다.

만약 트리 자료구조를 알지 못하면 

https://www.programmingstory.com/2024/02/blog-post_11.html

이전 포스팅을 먼저 보고 오자.


3. 풀이

우선 트리 구조를 구현하기 위해서 Node class를 사용했다. 자바에서는 구조체와 같은 역할을 하는 것이 class이기 때문에 클래스를 하나 더 만들어주었다. 

 

필요한 요소는 왼쪽 자식 노드와 오른쪽 자식 노드이기 때문에

다음과 같이 코드를 작성할 수 있다.


class Node {
    int left, right;
    Node(int left, int right) {
        this.left = left;
        this.right = right;
    }
}

그리고 만약 자식 노드가 없다면 해당 노드의 값은 -1로 표시하여 leaf node인지 아닌지를 판단할 수 있어야 한다. 

 

그래서 post-order, in-order, pre-order를 할 때도 -1의 값이 나오면 값을 return 해주면서 끝을 알릴 수 있어야 한다. 

여기서 각각의 함수를 static으로 만들고 호출해줄 것인데, 사실 코드는 거의 유사하다. 현재 노드를 출력하는 출력 라인의 순서만 달라지는 것이다. 

 


1] preorder 함수

 static void preorder( int x) {
        if (x == -1) return;
        System.out.print((char)(x+'A'));
        preorder(a[x].left);
        preorder(a[x].right);
    }

preorder 함수는 먼저 현재 노드를 출력해주고, 좌측 자식노드와 우측 자식노드를 차례대로 출력해준다.

노드의 값이 -1이라면 더 이상 자식 노드가 없다는 뜻이므로 return 해준다.

 

2] inorder 함수

static void inorder(int x) {
        if (x == -1) return;
        inorder(a[x].left);
        System.out.print((char)(x+'A'));
        inorder(a[x].right);
    }

inorder는 좌측 자식 노드를 출력, 현재 노드 출력, 우측 자식 노드를 출력하는 식으로 이루어진다.

노드의 값이 -1이라면 preorder와 마찬가지로 자식 노드가 없다는 뜻이므로 return 해준다.

 

3] postorder 함수

 static void postorder(int x) {
        if (x == -1) return;
        postorder(a[x].left);
        postorder(a[x].right);
        System.out.print((char)(x+'A'));
    }

postorder는 현재 노드를 가장 마지막에 출력해주는 것이다. 즉, 좌측 자식 노드와 우측 자식 노드 부분을 먼저 다 출력한 다음에 출력해준다. 노드의 값이 -1이라면 preorder와 마찬가지로 자식 노드가 없다는 뜻이므로 return 해준다.

 


4. 코드

이런식으로 비슷하게 세 가지 함수를 비슷하게 코드 작성해줄 수 있다.

전체 코드를 살펴보면, 다음과 같다.

import java.util.*;
class Node {
    int left, right;
    Node(int left, int right) {
        this.left = left;
        this.right = right;
    }
}
public class Main{
    static Node[] a;
    static void preorder( int x) {
        if (x == -1) return;
        System.out.print((char)(x+'A'));
        preorder(a[x].left);
        preorder(a[x].right);
    }
    static void inorder(int x) {
        if (x == -1) return;
        inorder(a[x].left);
        System.out.print((char)(x+'A'));
        inorder(a[x].right);
    }
    static void postorder(int x) {
        if (x == -1) return;
        postorder(a[x].left);
        postorder(a[x].right);
        System.out.print((char)(x+'A'));
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        a=new Node[26];
        for(int i=0; i<n; i++){
            int current=sc.next().charAt(0)-'A';
            char le=sc.next().charAt(0);
            char ri=sc.next().charAt(0);
            
            int left = -1;
            int right = -1;
            if (le != '.') {
                left = le-'A';
            }
            if (ri != '.') {
                right = ri-'A';
            }
            a[current] = new Node(left, right);
        }
        preorder(0);
        System.out.println();
        inorder(0);
        System.out.println();
        postorder(0);
        System.out.println();
    }
}


2월 28, 2024

[백준] 14500 테트로미노 문제 풀어보기

1. 문제

1) 링크

www.acmicpc.net/problem/14500

2) 문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

  • 정사각형은 서로 겹치면 안 된다.
  • 도형은 모두 연결되어 있어야 한다.
  • 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.



아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

3) 입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

4) 출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

 

더 자세한 문제의 제한을 보기 위해서는 위의 백준 링크를 클릭해보자.


2. 풀이

이 문제는 처음에 테트로미노를 다섯가지 종류에 대해서 90도씩 돌리는 모든 경우를 생각해볼 수 있다. 하지만 그렇게 접근을 하게 되면 경우의 수가 너무 많게 되는 문제가 생긴다. 코드를 쓰다가 오류를 범할 확률이 높아진다.

 

따라서 조금 더 쉽게 접근하기 위해서 이 문제는 테트로미노를 두 가지 종류로 나누어서 생각할 수 있다. 위의 그림에서 보라색 벽돌을 제외한 모든 테트로미노는 하나의 칸에서 시작하여 4칸을 총 이동하면 만들어지는 테트로미노이다. 그렇기 때문에 파란색, 노란색, 주황색, 연두색 테트로미노는 모두 재귀함수를 활용하여 문제를 해결 할 수 있다. 

 

public static void algo(int x, int y, int sum, int count){
        if(count==4){
            if (ans<sum){
                ans=sum;
            }
            return;
        }
        for(int i=0; i<4; i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if (nx>=0 && ny>=0 &&nx<n && ny<m && !check[nx][ny]){
                check[x][y]=true;
                algo(nx, ny, sum+a[x][y], count+1);
            }
            check[x][y]=false;
        }
    }

재귀함수 부분의 코드만 살펴보겠다. 우선 총 count가 4번이 되면 테트로미노 하나를 완성했다는 뜻이므로 이때 값이 max인지를 확인하여 답을 업데이트해주는 과정을 거친다. 

 

그리고 해당 칸이 방문되었는지를 확인하기 위해서 check 배열을 만들어주고 다음 칸이 범위 안에 있고 방문하지 않았을 경우에 다음 칸을 방문해준다. 이 경우에 sum을 업데이트해주고 count의 값은 하나를 증가시켜주면서 재귀함수를 호출하는 것이다. 


위의 재귀함수를 쓰면 파란색, 노란색, 주황색, 초록색 테트로미노의 경우는 모두 해결할 수 있다. 하지만 보라색 테트로미노의 경우 하나의 칸에서 시작하여서 4개의 칸을 모두 재귀함수로는 방문할 수 없다는 문제점이 생긴다. 

따라서 이 경우에만 특수하게 직접 모든 경우를 고려해주어 코드를 추가적으로 작성해준다. 

 

if (i+2 < n) {  //세로로 세워져있을 경우
        int temp = a[i][j] + a[i+1][j] + a[i+2][j];
 if (j+1 < m) { //오른쪽으로 돌출
   int temp2 = temp + a[i+1][j+1];
      if (ans < temp2) ans = temp2;
 }
  if (j-1 >= 0) { //왼쪽으로 돌출
     int temp2 = temp + a[i+1][j-1];
if (ans < temp2) ans = temp2;
   }
   }
 if (j+2 < m) { //가로로 눕혀있을 경우
  int temp = a[i][j] + a[i][j+1] + a[i][j+2];
  if (i-1 >= 0) { //아래로 향함
    int temp2 = temp + a[i-1][j+1];
  if (ans < temp2) ans = temp2;
                    }
    if (i+1 < n) { //위로 향함
        int temp2 = temp + a[i+1][j+1];
   if (ans < temp2) ans = temp2;
                    }
                }

이런식으로 작성해 줄 수 있다. 위의 재귀함수도 호출하고, 위의 코드도 실행해주면 모든 경우에 대해서 최댓값을 구할 수 있다. 


3. 코드

이를 모두 종합한 전체코드는 아래와 같다.

import java.util.*;

public class Main{
    public static int a[][];
    static boolean check[][];
    static int ans=0;
    static int n;
    static int m;
    static int []dx={1,-1,0,0};
    static int []dy={0,0,1,-1};
    public static void algo(int x, int y, int sum, int count){
        if(count==4){
            if (ans<sum){
                ans=sum;
            }
            return;
        }
        for(int i=0; i<4; i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if (nx>=0 && ny>=0 &&nx<n && ny<m && !check[nx][ny]){
                check[x][y]=true;
                algo(nx, ny, sum+a[x][y], count+1);
            }
            check[x][y]=false;
        }
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
         n=sc.nextInt();
         m=sc.nextInt();
         a=new int[n][m];
        check=new boolean[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                a[i][j]=sc.nextInt();
                            
            }
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                algo(i,j,0,0);
                if (i+2 < n) {
                    int temp = a[i][j] + a[i+1][j] + a[i+2][j];
                    if (j+1 < m) {
                        int temp2 = temp + a[i+1][j+1];
                        if (ans < temp2) ans = temp2;
                    }
                    if (j-1 >= 0) {
                        int temp2 = temp + a[i+1][j-1];
                        if (ans < temp2) ans = temp2;
                    }
                }
                if (j+2 < m) {
                    int temp = a[i][j] + a[i][j+1] + a[i][j+2];
                    if (i-1 >= 0) {
                        int temp2 = temp + a[i-1][j+1];
                        if (ans < temp2) ans = temp2;
                    }
                    if (i+1 < n) {
                        int temp2 = temp + a[i+1][j+1];
                        if (ans < temp2) ans = temp2;
                    }
                }
                
            }
        }
        System.out.println(ans);
    }
}

2월 28, 2024

[백준] 2667번 단지번호붙이기 문제 그래프로 풀어보기

1. 문제

1) 링크

www.acmicpc.net/problem/2667

2) 문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

3) 입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

4) 출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

 

문제의 세부 조건들을 확인하려면 위의 링크에 들어가서 확인해보자.


2. 풀이

이 문제는 단지를 나누는 것이기 때문에

https://www.programmingstory.com/2024/02/11724.html

연결요소의 개수를 구하는 문제와 유사하다. 

다른 점은 특정 점을 기준으로 위, 아래, 오른쪽, 왼쪽 칸 네가지를 살펴보아야 한다는 것이다. 

이 문제는 그래프 유형으로 BFS, DFS로 모두 풀 수 있는데 나는 오늘 DFS로 풀어보았다.

 

이 문제를 풀기 위한 준비 배열은,

 

1. static int[][]a; (문제에서 해당 칸이 1인지 0인지를 받기 위한 배열)

 

2. static int[][]group; (해당 칸이 몇 번째 단지인지를 알기 위한 배열)

 

3.  static final int[] dx={0,0,1, -1};
    static final int[] dy={1,-1,0,0}; 
    네가지 경우로 위,아래, 왼쪽, 오른쪽을 검사하기 위해 필요한 배열

 

4. int ans[]=new int[cnt]; (각 단지마다 몇개의 집이 있는지를 카운트하기 위한 배열)

 

이렇게 네가지가 필요하다. 

이 문제는 우선 해당 칸마다 group 배열에 몇 단지인지를 모두 다 적어놓고,

이후에 다시 모든 칸을 이중 for문으로 돌면서 집의 개수를 세어주는 식으로 진행할 것이다.

 

따라서 먼저 dfs 함수부터 살펴보자면,

  public static void dfs(int i, int j, int cnt){
        group[i][j]=cnt;
        for(int k=0; k<4; k++){
            int nx=i+dx[k];
            int ny=j+dy[k];
            if(nx>=0 && ny>=0 && nx<=(n-1)&&ny<=(n-1)){
                if (a[nx][ny]==1 &&group[nx][ny]==0){
                      dfs(nx,ny,cnt);
                }
              
            }
        }
    }

위와 같다. 해당 group 배열에 단지의 수를 적어놓고 위, 아래, 오른쪽, 왼쪽의 집이 같은 단지인지를 파악하는 과정을 거치면 된다. 해당 칸의 a 배열이 1이고 group이 0이라는 소리는 집이 있는데 단지에 배정이 안되었으므로 재귀로 다음 dfs함수를 호출해야 한다.


최종 몇 단지까지 있는지는

for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if (a[i][j]==1 &&group[i][j]==0){
                    dfs(i, j, ++cnt);
                }
            }
        }

위의 코드처럼 구할 수 있다. cnt (단지수)를 하나씩 증가시키면서 dfs 함수를 호출시키는 과정이다.


이 과정을 다 한 이후에는 cnt (단지수)가 확정이 되었고, 각 단지에 몇 가구가 있는지를 판단하는 과정이 필요하다. 이는 group 배열에 단지가 다 적혀있으므로 모든 칸을 순회하면서 가구의 수를 세어주면 된다.

 int ans[]=new int[cnt];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if (group[i][j]!=0){
                    ans[group[i][j]-1]++;
                }
            }
        }

위에처럼 해당 단지 index에 해당하는 가구를 증가시킨다.


3. 코드

이 모든 과정을 종합하여 전체 코드를 살펴보면,

import java.util.*;

public class Main{
    static int[][]a;
    static int[][]group;
    static int n;
    static final int[] dx={0,0,1, -1};
    static final int[] dy={1,-1,0,0};
    public static void dfs(int i, int j, int cnt){
        group[i][j]=cnt;
        for(int k=0; k<4; k++){
            int nx=i+dx[k];
            int ny=j+dy[k];
            if(nx>=0 && ny>=0 && nx<=(n-1)&&ny<=(n-1)){
                if (a[nx][ny]==1 &&group[nx][ny]==0){
                      dfs(nx,ny,cnt);
                }
              
            }
        }
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
         n=sc.nextInt();
        a=new int[n][n];
        group=new int[n][n];
        for(int i=0; i<n; i++){
            String s=sc.next();
            for(int j=0; j<n; j++){
                a[i][j]=s.charAt(j)-'0';
            }
        }
        int cnt=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if (a[i][j]==1 &&group[i][j]==0){
                    dfs(i, j, ++cnt);
                }
            }
        }
        int ans[]=new int[cnt];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if (group[i][j]!=0){
                    ans[group[i][j]-1]++;
                }
            }
        }
        Arrays.sort(ans);
      System.out.println(cnt);
        for (int i=0; i<cnt; i++) {
            System.out.println(ans[i]);
        }
        
    }
}

위처럼 계산할 수 있다.

 

이 문제에서는 그래프로 푸는 방법도 중요하지만 

static final int[] dx={0,0,1, -1}; 
static final int[] dy={1,-1,0,0}; 

위처럼 배열을 만들어 4번의 for문을 돌면서 행과 열의 index를 변화시키는 방법도 많이 사용되니 익혀두자. 

이 문제는 왼쪽, 오른쪽, 위, 아래로만 움직이지만 대각선까지 움직일 수 있는 조건을 가진 문제도 있다. 

아래 링크의 백준 4963번이며 이와 관련된 포스팅은 별도로 해보도록 하겠다.

www.acmicpc.net/problem/4963



2월 28, 2024

[백준] 14226번 이모티콘 문제 BFS의 변형

1. 문제

1) 링크

www.acmicpc.net/problem/14226

2) 문제

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

  1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
  2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
  3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

3) 입력

첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

4) 출력

첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

 

문제의 세부조건을 더 알아보기 위해서는 위의 링크에 들어가서 확인해보자.


 2. 풀이

이 문제는 중요한 변수가 크게 두 가지가 있다. 첫번째는 화면에 있는 이모티콘의 개수, 두번째는 클립보드에 있는 이모티콘의 개수이다. 할 수 있는 연산 또한 클립보드의 개수에 따라서 결과가 달라지기 때문에 이 문제는 화면이모티콘의 개수와 클립보드에 있는 이모티콘의 개수를 함께 queue에 넣어주어야 한다. while문을 돌때도 두 개를 함께 pop 해주어야 한다는 것을 알 수 있다. 

 

그렇다면, 할 수 있는 시행을 하나씩 보면서 화면이모티콘의 개수와 클립보드 이모티콘의 개수가 어떻게 변화하는지 알아보자

  1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. : (화면, 클립) --> (화면, 화면)
  2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.: (화면, 클립)--> (화면+클립, 클립)
  3. 화면에 있는 이모티콘 중 하나를 삭제한다. : (화면, 클립)--> (화면-1, 클립)

위와 같이 변한다는 것을 알 수 있다. 

시작은 화면이모티콘 1개와 클립보드 이모티콘 0개로 시작한다. 

따라서 queue 에 1과 0을 각각 push해준 채로 시작하면 된다.

 

그리고 가능한 3가지의 경우를 모두 다 queue로 처리해준다.

 while(!q.isEmpty()){
  int s=q.remove();
    int c=q.remove();
    if (time[s][s]==-1){ //첫번째 복사
   time[s][s]=time[s][c]+1;
  q.add(s);q.add(s);
            }
   if (s+c<=goal&&time[s+c][c]==-1){ //두번째 붙여넣기
     time[s+c][c]=time[s][c]+1;
     q.add(s+c); q.add(c);
            }
    if (s>=1 && time[s-1][c]==-1){ //세번째 삭제
  time[s-1][c]=time[s][c]+1;
q.add(s-1); q.add(c);
            }
        }

세가지를 모두 다 처리하면 위와 같다.

대부분의 bfs 문제는 한 가지 변수만 queue로 처리하지만 이 경우는 답이 두 가지 변수에 의해 영향을 받기 때문에 두 가지를 queue에 push, pop해준다는 점이 특이하다.

 

3. 코드 

전체 코드를 살펴보면 아래와 같다. 

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int goal=sc.nextInt();
        int time[][]=new int[goal+1][goal+1]; // 화면이모티콘과 클립보드 이모티콘 개수 저장
        for(int i=0; i<=goal; i++){
            for(int j=0; j<=goal; j++){
                time[i][j]=-1; //처음 시간은 -1로 초기화
            }
        }
        Queue<Integer> q= new LinkedList<>();
        q.add(1);
        q.add(0);
        time[1][0]=0;
        while(!q.isEmpty()){
            int s=q.remove();
            int c=q.remove();
            if (time[s][s]==-1){
                time[s][s]=time[s][c]+1;
                q.add(s);q.add(s);
            }
            if (s+c<=goal&&time[s+c][c]==-1){
                time[s+c][c]=time[s][c]+1;
                q.add(s+c); q.add(c);
            }
            if (s>=1 && time[s-1][c]==-1){
                time[s-1][c]=time[s][c]+1;
                q.add(s-1); q.add(c);
            }
        }
        int ans=-1;
        for(int i=0; i<=goal; i++){
            if (time[goal][i]!=-1){
                if ((ans==-1)|| (ans> time[goal][i])){
                ans=time[goal][i];
            }
            }
            
        }
        System.out.println(ans);
    }
}