JUnit 를 이론적으로만 공부하는 것은 한계가 있다고 생각이 늘었고 막상 프로젝트의 일부분을 따와서 적용해보려 시도하니 예상하지 못하는 예외가 너무 많이 발생했다.

JUnit를 중점적으로 연습하기 위해 간단하게 새 프로젝트를 생성하고 사용해보자.

프로젝트의 기능은 은행 거래를 간단하게 구현하는 것을 목적으로 두고 있다.

🔧 기본 설정

진행하기 위한 간단한 기본 설정들에 대해서 언급하고 지나가도록 하자.

🎨 화면 (UX Design)

📁 Database 설정

데이터 베이스는 User, Account, Transaction으로 간단하게 진행한다.

⏰ LocalDate 설정

Jpa LocalDateTime 자동으로 LocalDateTime 생성 하는 법

• @EnableJpaAuditing //날짜 기입 어노테이션 , (Main Class 적용)
• @EntityListeners(AuditingEntityListener.class) (Entity Class 적용)

    @CreatedDate
    @Column(nullable = false)
    private LocalDateTime createdAt;

    @LastModifiedBy
    @Column(nullable = false)
    private LocalDateTime updateAt;

JUnit 테스트를 편하게 사용하기 위해 시간 Entity를 따로 분리하여 상속해서 사용하지는 않았다.

🧩 User Entity

import lombok.Builder;
import lombok.Getter;
import lombok.NoArgsConstructor;
import org.springframework.data.annotation.CreatedDate;
import org.springframework.data.annotation.LastModifiedBy;
import org.springframework.data.jpa.domain.support.AuditingEntityListener;

import javax.persistence.*;
import java.time.LocalDateTime;

@NoArgsConstructor //스프링이 User 객체 생성할 때 반 생성자로 new를 하기 때문
@Getter
@EntityListeners(AuditingEntityListener.class) //@CreatedDate , @LastModifiedBy 자동 기입하기 위해 설정
@Table(name = "user_tb")
@Entity
public class User { //extends 시간설정 (상속)
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @Column(unique = true , nullable = false , length = 20)
    private String username;

    @Column(nullable = false , length = 60) //패스워드 인코딩 시 길이가 증가 하기 때문에 넉넉하게 할당
    private String password;

    @Column(nullable = false , length = 20)
    private String email;

    @Column(nullable = false , length = 20)
    private String fullname;

    @Enumerated(EnumType.STRING)
    @Column(nullable = false)
    private UserEnum role; //ADMIN , CUSTOMER

    @CreatedDate //Insert
    @Column(nullable = false)
    private LocalDateTime createdAt;

    @LastModifiedBy //Insert, Update
    @Column(nullable = false)
    private LocalDateTime updateAt;

    @Builder
    public User(Long id, String username, String password, String email, String fullname, UserEnum role, LocalDateTime createdAt, LocalDateTime updateAt) {
        this.id = id;
        this.username = username;
        this.password = password;
        this.email = email;
        this.fullname = fullname;
        this.role = role;
        this.createdAt = createdAt;
        this.updateAt = updateAt;
    }
}

🧩 Account Entity

import lombok.Builder;
import lombok.Getter;
import lombok.NoArgsConstructor;
import org.springframework.data.annotation.CreatedDate;
import org.springframework.data.annotation.LastModifiedBy;
import org.springframework.data.jpa.domain.support.AuditingEntityListener;
import shop.mtcoding.bank.domain.user.User;

import javax.persistence.*;
import java.time.LocalDateTime;

@NoArgsConstructor //스프링이 User 객체 생성할 때 반 생성자로 new를 하기 때문
@Getter
@EntityListeners(AuditingEntityListener.class) //@CreatedDate , @LastModifiedBy 자동 기입하기 위해 설정
@Table(name = "account_tb")
@Entity
public class Account {
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @Column(unique = true, nullable = false, length = 20)
    private Long number; //계좌 번호

    @Column(nullable = false, length = 4)
    private Long password; //계좌 비밀번호

    @Column(nullable = false)
    private Long balance; //잔액 (기본값 1000원)

    // 항상  ORM 에서 FK의 주인은 Many Entity 쪽 이다.
    //account.getUser().아무필드호출() -> Lazy 발동 , 조회
    //getUser() 까지도 호출 되지 않는다.
    @ManyToOne(fetch = FetchType.LAZY) //지연로딩
    private User user;

    @CreatedDate //Insert
    @Column(nullable = false)
    private LocalDateTime createdAt;

    @LastModifiedBy //Insert, Update
    @Column(nullable = false)
    private LocalDateTime updateAt;

    @Builder
    public Account(Long id, Long number, Long password, Long balance, User user, LocalDateTime createdAt, LocalDateTime updateAt) {
        this.id = id;
        this.number = number;
        this.password = password;
        this.balance = balance;
        this.user = user;
        this.createdAt = createdAt;
        this.updateAt = updateAt;
    }
}

🧩 Transaction Entity

package shop.mtcoding.bank.domain.transaction;

import lombok.Builder;
import lombok.Getter;
import lombok.NoArgsConstructor;
import org.springframework.data.annotation.CreatedDate;
import org.springframework.data.annotation.LastModifiedBy;
import org.springframework.data.jpa.domain.support.AuditingEntityListener;
import shop.mtcoding.bank.domain.account.Account;

import javax.persistence.*;
import java.time.LocalDateTime;

@NoArgsConstructor //스프링이 User 객체 생성할 때 반 생성자로 new를 하기 때문
@Getter
@EntityListeners(AuditingEntityListener.class) //@CreatedDate , @LastModifiedBy 자동 기입하기 위해 설정
@Table(name = "transaction_tb")
@Entity
public class Transaction {
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;
    @JoinColumn(foreignKey = @ForeignKey(ConstraintMode.NO_CONSTRAINT))
    //논리적으로만 외래키를 맺고 물리적으로는 외래키를 맺지 않음
    @ManyToOne(fetch = FetchType.LAZY)
    private Account withdrawAccount;
    @JoinColumn(foreignKey = @ForeignKey(ConstraintMode.NO_CONSTRAINT))
    @ManyToOne(fetch = FetchType.LAZY)
    private Account depositAccount;

    private Long amount;

    //이체나 출금 당시 금액을 남겨 놓기 위함
    private Long withdrawAccountBalance;
    private Long depositAccountBalance;

    @Enumerated(EnumType.STRING)
    @Column(nullable = false)
    private TransactionEnum gubun;

    //계좌가 사라져도 로그는 남아야 한다.
    private String sender;
    private String receiver;
    private String tel;

    @CreatedDate //Insert
    @Column(nullable = false)
    private LocalDateTime createdAt;

    @LastModifiedBy //Insert, Update
    @Column(nullable = false)
    private LocalDateTime updateAt;

    @Builder
    public Transaction(Long id, Account withdrawAccount, Account depositAccount, Long amount, Long withdrawAccountBalance, Long depositAccountBalance, TransactionEnum gubun, String sender, String receiver, String tel, LocalDateTime createdAt, LocalDateTime updateAt) {
        this.id = id;
        this.withdrawAccount = withdrawAccount;
        this.depositAccount = depositAccount;
        this.amount = amount;
        this.withdrawAccountBalance = withdrawAccountBalance;
        this.depositAccountBalance = depositAccountBalance;
        this.gubun = gubun;
        this.sender = sender;
        this.receiver = receiver;
        this.tel = tel;
        this.createdAt = createdAt;
        this.updateAt = updateAt;
    }
}

📝 Security 설정

Security 설정을 하지 않고 8081번 포트에 접속할 경우 Security에서 자체적으로 제공하는 로그인 화면에 가려진다.

Security에서 기본적으로 적용되는 조건을 풀고 임의로 커스텀 하기 위해 추가적인 설정 값이 필요하다.

📑 SecurityConfig

기본적으로 Springboot Security의 Default 설정들만 작성하고 추후 수정하면서 진행 하도록 할 것 이다.

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.security.config.annotation.web.builders.HttpSecurity;
import org.springframework.security.config.http.SessionCreationPolicy;
import org.springframework.security.crypto.bcrypt.BCryptPasswordEncoder;
import org.springframework.security.web.SecurityFilterChain;
import org.springframework.web.cors.CorsConfiguration;
import org.springframework.web.cors.CorsConfigurationSource;
import org.springframework.web.cors.UrlBasedCorsConfigurationSource;
import shop.mtcoding.bank.domain.user.UserEnum;

@Configuration //설정파일 Bean 등록
public class SecurityConfig {
    private final Logger log = LoggerFactory.getLogger(getClass());

    //로그 찍어내기 위함
    @Bean //IoC 컨테이너에 BCryptPasswordEncoder() 객체가 등록됨.
    public BCryptPasswordEncoder passwordEncoder() {
        log.debug("디버그 : BCryptPasswordEncoder 빈 등록됨");
        return new BCryptPasswordEncoder();
    }

    //JWT 필터 등록 추가 구현 필요

    //JWT 서버 생성, Session 사용 안함
    @Bean
    public SecurityFilterChain filterChain(HttpSecurity http) throws Exception {
        http.headers().frameOptions().disable(); //iframe 허용 안함

        http.csrf().disable(); // enable 상태 이면 post맨 작동 안함

        http.cors().configurationSource(configurationSource()); //교차 플랫폼 접근 허용

        //jSessionId를 서버에서 관리하지 않음
        http.sessionManagement().sessionCreationPolicy(SessionCreationPolicy.STATELESS);

        //react, 앱 , Security에서 제공하는 기본 로그인 방식을 사용하지 않음
        http.formLogin().disable();

        //httpBasic은 브라우저가 팝업창을 이용해서 사용자 인증을 진행 한다. , disable 설정
        http.httpBasic().disable();

        http.authorizeRequests()
                .antMatchers("/api/s/**").authenticated() //s가 붙은 API는 인증 해야 한다.
                // 최근 공식문서에는 ROLE_ 붙이지 않아도 된다.
                .antMatchers("/api/admin/**").hasRole("" + UserEnum.ADMIN)
                .anyRequest().permitAll(); // 나머지 요청은 허용

        return http.build();
    }

    public CorsConfigurationSource configurationSource(){
        CorsConfiguration configuration = new CorsConfiguration();
        configuration.addAllowedHeader("*");
        configuration.addAllowedMethod("*"); //GET, POST, PUT, DELETE (Javascript 요청 허용)
        configuration.addAllowedOriginPattern("*"); //모든 IP 주소 허용 (프론트 엔드  IP만 허용 react)
        configuration.setAllowCredentials(true); // 클라이언트 쿠키 요청 허용

        UrlBasedCorsConfigurationSource source = new UrlBasedCorsConfigurationSource();
        source.registerCorsConfiguration("/**", configuration);
        return source;
    }
}

📌 CSRF

CSRF는 Cross Site Request Forgery(사이트 간 요청 위조)의 줄임말로 웹 취약점 중 하나이다.

공격자가 희생자의 권한을 도용하여 특정 웹 사이트의 기능을 실행하게 할 수 있으며 이는 희생자의 의도와는 무관하게 이루어진다.

Config 에서는 Postman을 통해서 진행 하기 때문에 열어두었다.

📌 CORS

예전 프로젝트를 진행할때 react와 springboot로 클라이언트와 서버를 구축 했었다.

API 요청 시 cors error가 발생했는데 이는 두 출처가 일치하지 않아 발생하는 것이다.

public CorsConfigurationSource configurationSource(){
        CorsConfiguration configuration = new CorsConfiguration();
        configuration.addAllowedHeader("*");
        configuration.addAllowedMethod("*"); //GET, POST, PUT, DELETE (Javascript 요청 허용)
        configuration.addAllowedOriginPattern("*"); //모든 IP 주소 허용 (프론트 엔드  IP만 허용 react)
        configuration.setAllowCredentials(true); // 클라이언트 쿠키 요청 허용

        UrlBasedCorsConfigurationSource source = new UrlBasedCorsConfigurationSource();
        source.registerCorsConfiguration("/**", configuration);
        return source;
    }

이번 프로젝트에서도 대부분의 Javascript 요청을 허용하고 진행 할 것이다.

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.context.ConfigurableApplicationContext;
import org.springframework.data.jpa.repository.config.EnableJpaAuditing;

@EnableJpaAuditing //날짜 기입 어노테이션
@SpringBootApplication
public class BankApplication {

    public static void main(String[] args) {
        ConfigurableApplicationContext context = SpringApplication.run(BankApplication.class, args);
        String[] iocNames = context.getBeanDefinitionNames();

        for (String name : iocNames) {
            System.out.println(name);
        }
    }

}

Bean이 정상적으로 작동 되는지 확인하기 위해 Main Class 에 위와 같이 수정 한 후 실행 한다.

새롭게 8081번 포트에 접속을 한다면

위와 같이 404 Not Found가 발생하는데 이는 클라이언트 화면을 만들지 않았기에 정상적인 Error Message 이다.

        http.authorizeRequests()
                .antMatchers("/api/s/**").authenticated() //s가 붙은 API는 인증 해야 한다.
                // 최근 공식문서에는 ROLE_ 붙이지 않아도 된다.
                .antMatchers("/api/admin/**").hasRole("" + UserEnum.ADMIN)
                .anyRequest().permitAll(); // 나머지 요청은 허용

접근 권한을 설정한 admin api 요청도 정상적으로 제한 되는것을 볼 수 있다.

🎯 입력

🎯 출력

♟️ 제출

🧐 문제 풀이

이번 문제를 풀때 가장 중요한 부분은 순환 구조이다.

문제에서 주어지는 순환선을 그래프로 표현 했을 경우 cycle이 된다고 생각했다.

하지만 모든 정점을 전부 하나씩 탐색해서 시작 지점으로 돌아온다면 시간복잡도에서 옳지 못한 결과를 낼 것 같아서 한번 사이클에 포함된 정점들은 탐새하지 않도록 하는 것이 좋을 것 같았다.

위 예제의 경우 시작점은 가장 작은 번호를 가진 번호인 1으로 시작 한다.

이후 1번 정점에 연결된 정점들은 2,3번 정점이다.

dfs로 연결된 정점을 파고 든다고 가정 해보자.

1번 정점으로 시작한 dfs를 통해 모든 정점들이 cycle에 포함됨을 알 수 있다.

위의 예제 그림은 모든 정점이 cycle에 포함되어 있기 때문에 더 다양한 예제를 통해서 진행 해보겠다.

마찬가지로 1번 정점부터 탐색한다고 가정 해보겠다.

초록색 화살표가 cycle이 형성되는 부분이고 빨간색 화살표가 dfs에서의 분기점이자 cycle이 형성 되지 않는 부분이다.

정점을 탐색하면서 모든 정점을 cycle에 포함된다고 flag를 체크 해주면서 진행하고 만약 cycle을 찾았다면 dfs를 중단하고 flag 값을 그대로 가져가면 될 것이다.

만약 cycle을 찾지 못했다면 flag를 원래대로 돌려주면 될 것이다.

🫤 의문점

♟️ 시작점이 cycle에 포함되지 않는 경우

만약 1번 지점이 cycle에 해당하지 않는 다면 flag는 false로 정상적으로 반환되는지 의문이 생겼다.

2번 정점으로 가는 화살표는 더이상 연결된 정점이 존재하지 않기 때문에 dfs는 종료 될 것 이다.

3번 정점으로 가는 화살표는 5번 정점으로 간다.

5번 정점에서 화살표는 자신의 정점 즉 5번으로 되돌아 오지만 시작점의 값은 여전히 1번으로 저장하고 있으므로 cycle이 형성되지 않았다고 판단하여 모든 flag를 되돌리면서 복귀 한다.

♟️ cycle이 여러개로 형성 되어 있는 경우

만약 cycle이 한개가 아닌 여러개가 문제에 주어진다면 이때까지의 풀이방법으로 해결이 가능한지 궁금했다.

하지만 정점 N개를 만족하면서 관계선도 N개를 만족 하기 위해서의 여러가지 cycle은 이 문제를 푸는데 까지 찾아내지 못해서 패스 했다.

🫧 제출 코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    static int N;
    static boolean[] isCycle;
    static ArrayList<Integer>[] graphs;
    static boolean[] visited;
    static int[] distFromCycle;

    static class Node{
        int num;
        int distance;

        public Node(int num, int distance) {
            this.num = num;
            this.distance = distance;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        N = Integer.parseInt(st.nextToken()); //세로

        isCycle = new boolean[N + 1];
        graphs = new ArrayList[N + 1];
        distFromCycle = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            graphs[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++) {
            StringTokenizer stD = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(stD.nextToken());
            int e = Integer.parseInt(stD.nextToken());

            graphs[s].add(e);
            graphs[e].add(s);
        }

        for (int i=1; i<=N; i++){
            if (checkCycle_dfs(i,i,i) == true){
                //Cycle 찾기
                break;
            }
        }

        for (int i=1; i<=N; i++){
            if (isCycle[i] == false){
                distFromCycle[i] = checkDistance_bfs(i);
            }
        }

        for (int i=1; i<=N; i++){
            bw.write(distFromCycle[i] + " ");
        }
        bw.write("\n");

        bw.flush();
        bw.close();
    }

    static int checkDistance_bfs(int start){
        visited = new boolean[N + 1];
        Queue<Node> q= new LinkedList<>();
        q.offer(new Node(start,0));
        visited[start] = true;

        while (!q.isEmpty()){
            Node now = q.poll();

            if (isCycle[now.num] == true){
                return now.distance;
            }
            for (int next : graphs[now.num]){
                if (visited[next] == false){
                    visited[next] = true;
                    q.offer(new Node(next,now.distance + 1));
                }
            }
        }

        return -1;
    }

    static boolean checkCycle_dfs(int start, int prev, int now) {
        isCycle[now] = true; //현재 노드 Cycle 포함

        for (int next : graphs[now]) {
            //현재 노드와 연결된 인접 노드 탐색

            if (isCycle[next] == false) {
                //인접 노드가 현재 Cycle 탐색에 포함되지 않은 새로운 노드 라면

                if (checkCycle_dfs(start,now,next)) {
                    return true;
                }
            } else if (prev != next && next == start) {
                //이전 노드가 다음 노드가 되는 무한 반복 방지
                //다음 노드가 시작 노드 라면 Cycle을 의미
                return true;
            }
        }

        isCycle[now] = false;
        //현재 노드는 cycle가 형성되지 않고 탐색이 종료 되었음
        return false;
    }
}

📌 입력

📌 출력

💻 제출

🤔 문제 풀이

📑 주어진 힌트

1. 고슴도치는 현재 있는 칸과 입전한 네 칸 중 하나로 이동할 수 있다.

-> 동 서 남 북 으로 좌표 이동이 가능하다고 해석 했다.

2. 물도 매분마다 비어있는 칸으로 확장한다.

-> 물도 동 서 남 북 좌표 이동이 가능하다.

3. 최소 시간을 구하는 프로그램

->최단거리 (다익스트라, 플로이드 워셜, 벨먼-포드) 또는 BFS 로 알고리즘 유형을 줄일 수 있고 해당 문제는 그래프 문제가 아니고 단순히 좌표를 이동하는 문제라고 판단해 BFS를 사용 하기로 했다. 4. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. -> 동일한 시간의 확장은 고슴도치 보다 물의 확장이 우선 되어야 한다. 물의 우선순위가 더 높다.

단순히 문제만 읽는 다면 여기까지 힌트를 얻을 수 있지만 이번 문제에서는 추가 힌트가 있다.

D와 S는 하나씩만 주어진다. -> * 즉 물은 여러개가 주어질 수 있다.

이번 문제를 해석할 때 물이 하나만 존재한다는 생각을 하고 있어서 어려움을 겪었다.

간단한 예제를 그림을 통해서 알아보겠다.

위 그림에서 초록색 영역은 비버를 뜻하는 최종 도착지

파란색 영역은 초기 물의 지점과 확장 영역

빨간색 영역은 초기 고슴도치 및 고슴도치의 확장 영역 이다.

보라색 영역은 고슴도치 와 물의 영역이 둘다 존재 하는 영역이고 고슴도치가 지나간 구역을 물이 덮어서 더이상 고슴도치가 이동하지 못하는 영역 이라는 뜻이다.

문제를 풀이 할때 물과 고슴도치의 확장을 매번 따로 분리해서 진행 할 수 있지만 우선순위 가중치를 둔다면 굳이 분리하지 않아도 된다고 생각했다.

해당 좌표의 값을 class로 저장하고 우선순위 가중치를 통해서 고슴도치와 물을 분리 하기로 했다.

static class Point {
        int x;
        int y;
        int cnt; //depth
        int priority;
        //물 = 1
        //고슴도치 = 2

        public Point(int x, int y, int cnt, int priority) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.priority = priority;
        }
    }

확장 시간(depth,cnt)이 다르다면 오름차순으로 진행 하면 될 것이고 같다면 물이 우선순위로 처리 되면 될 것 이다.

해당 우선순위를 제어 하기 위해 우선순위 큐를 사용하였다.

📝 제출 코드

import java.io.*;
import java.util.*;


public class Main {
    static int N, M;
    static Point D, S;
    static char[][] map;
    static int[] dx = {0, 0, 1, -1}; //동 서 남 북
    static int[] dy = {1, -1, 0, 0}; //동 서 남 북
    static boolean[][] visited;
    static ArrayList<Point> waters = new ArrayList<>();

    static class Point {
        int x;
        int y;
        int cnt; //depth
        int priority;
        //물 = 1
        //고슴도치 = 2

        public Point(int x, int y, int cnt, int priority) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.priority = priority;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        visited = new boolean[N][M];

        for (int x = 0; x < N; x++) {
            String line = br.readLine();
            for (int y = 0; y < M; y++) {
                char data = line.charAt(y);
                if (data == 'D') {
                    D = new Point(x, y, 0, 0);
                } else if (data == 'S') {
                    S = new Point(x, y, 0, 2);
                } else if (data == '*') {
                    waters.add(new Point(x,y,0,1)); //물의 개수는 여러개
                }
                map[x][y] = data;
            }
        }
        int result = bfs();

        bw.write(result != -1 ? result + "\n" : "KAKTUS\n");

        bw.flush();
        bw.close();
    }

    static int bfs() {
        PriorityQueue<Point> pq = new PriorityQueue<>(
                (a, b) ->
                        a.cnt == b.cnt ? Integer.compare(a.priority, b.priority) : Integer.compare(a.cnt, b.cnt)
                //depth,cnt(이동 횟수) 최우선
                //고슴도치 보다 물이 더 큰 우선순위를 가짐
        );

        for (Point water : waters){
            pq.offer(water);
            visited[water.x][water.y] = true; //초기 물 방문 True
        }

        pq.offer(S);
        visited[S.x][S.y] = true; //초기 고슴도치 방문 True

        while (!pq.isEmpty()) { //큐가 비어있지 않다면 반복

            Point now = pq.poll();

            if (now.x == D.x && now.y == D.y) { //도착지에 도착했다면
                return now.cnt;
            }

            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];


                if (isRange(nx,ny)){
                    if (visited[nx][ny] == false && map[nx][ny] != 'X') {

                        if (now.priority == 1 && nx == D.x && ny == D.y) {
                            //현재 물의 이동이 진행중이며 다음 영역이 비버 영역이라면 Continue
                            continue;
                        }

                        visited[nx][ny] = true;
                        pq.offer(new Point(nx, ny, now.cnt + 1, now.priority));
                    }
                }
            }
        }

        return -1;
    }

    static boolean isRange(int x, int y) {
        return 0 <= x && 0 <= y && x < N && y < M;
    }


}

📌 입력

📌 출력

💻 제출

🤔 문제 풀이

해당 문제를 풀때 몇 가지의 단서가 존재한다.

1. 일방통행 도로 라는 말은 방향성이 존재하는 그래프 라는 뜻으로 해석 할 수 있다. 따라서 ArrayList 배열을 통해서 각 정점간의 방향 간선을 입력하기로 했다.

2. 1번 지점에서 시작 하여 1번 지점으로 되돌아 와야 하기 때문에 시작점은 1으로 고정 값이다. 1으로 시작하여 탐색을 진행하고 탐색 도중 다음 정점이 1이라면 cycle이 형성 되는 것 이다.

3. cycle이 형성되는 최단 경로를 구하는 것이 아닌 최대한 많은 값을 가지는 경로를 구해야 한다.

위상 정렬을 사용한다면 2번 정점을 탐색 하기 이전 아래 두 계산이 가능하다.

1. 1번 정점 까지의 가중치 + 1번 에서 2번 까지의 가중치
2. 3번 정점 까지의 가중치 + 3번 에서 2번 까지의 가중치

위 두가지의 값을 비교 해서 큰 가중치 값을 2번 정점에 저장 할 수 있다.

가중치 값을 저장할 때 이전 정점 번호를 저장한다면 역방향 탐색이 가능하다. (1, 3번 정점의 가중치 값이 동일 하다고 가정 할 때 2번 정점 이전 노드는 3번 정점 이다.)

문제에서 주어진 예제를 통해서 설명 해보겠다.

1번 정점을 위상 정렬 탐색 시에 indegree 가 0인 정점은 2와 3이다.

2번 정점을 탐색 시에 5번 정점의 indegree는 0이 되고 6번 정점의 indegree는 1 감소한다. (3번 정점은 대기 상태)

2번 정점의 이전 정점의 값은 1로 저장 될 것 이다.

3번 노드 탐색 시 이전 정점의 값은 1이 될 것이다.

5번 노드 탐색 시에 6번 노드의 indegree가 0이 될 것이며 연결 되어 있는 이전 정점들 중 가장 가중치가 큰 노드는 5번 노드 이다.

위와 과정을 반복 했을 경우

4번 정점의 이전 정점은 6번과 7번 정점 중 가장 가중치가 높은 정점이 저장 될 것이며 4번 정점 탐색 시 다음 indegree가 0인 정점은 1번 정점이다.

1번 정점이 다시 탐색 될 경우 cycle이 형성 된 것이고 1의 이전 정점으로 4번 정점이 저장 된 후 종료 된다.

로직이 종료 된다면 1번 부터 역순으로 이전 정점을 돌아가면서 순서를 저장 한 후 뒤집어 준다.

📝 제출 코드

import java.io.*;
import java.util.*;


public class Main {
    static int N, M;
    static ArrayList<Node>[] graph;
    static int[] inDegree, score, prev;
    static Deque<Integer> dq = new ArrayDeque<>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static class Node {
        int num;
        int cost;

        public Node(int num, int cost) {
            this.num = num;
            this.cost = cost;
        }
    }

    public static void main(String[] args) throws IOException {


        N = Integer.parseInt(br.readLine()); //정점 수
        M = Integer.parseInt(br.readLine()); //간선 수

        graph = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        inDegree = new int[N + 1];

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

            int s = Integer.parseInt(stD.nextToken());
            int e = Integer.parseInt(stD.nextToken());
            int v = Integer.parseInt(stD.nextToken());

            graph[s].add(new Node(e, v));
            inDegree[e]++;
        }

        solved();

        bw.write(print() + "\n");

        bw.flush();
        bw.close();
    }

    static void solved(){
        score = new int[N + 1];
        prev = new int[N + 1];

        dq.offerLast(1); // 시작 정점 = 1

        while (!dq.isEmpty()){
            Integer now = dq.pollFirst();

            for (Node next : graph[now]){
                int nextCost = score[now] + next.cost;

                if (score[next.num] < nextCost){
                    score[next.num] = nextCost;
                    prev[next.num] = now;
                }

                inDegree[next.num]--;

                if (inDegree[next.num] == 0 && (next.num != 1)){
                    dq.offerLast(next.num);
                }
            }
        }
    }

    static String print() throws IOException{
        bw.write(score[1] + "\n");

        StringBuilder sb = new StringBuilder();

        int num = 1;
        while (true){
            if (prev[num] == 1){
                dq.offerLast(1);
                break;
            }

            dq.offerLast(prev[num]);
            num = prev[num];
        }

        while (!dq.isEmpty()){
            sb.append(dq.pollLast()).append(' ');
        }

        sb.append("1 ");

        return sb.toString();
    }

}

📗 정리

위상 정렬, 플로이드 워셜, 유니온 파인드 와 같은 그래프 문제들은 평균적으로 골드 2 ~ 3 이상의 수준을 가지는 것 같으며 경우에 따라 DP가 적용되는 부분도 존재 하는데 DP는 풀어도 풀어도 적응이 되지 않는다.

문제를 볼 때 DP를 통해서 시간 관리를 해야겠다는 생각이 든 순간 문제를 풀 수 있는 다른 알고리즘을 필사적으로 찾는 것 같다.

꾸준히 익숙해져야 할 듯 하다..

📌 입력

📌 출력

🤔 풀이 까지의 생각

문제에서 얻을 수 있는 힌트는 모두 주워 담아보자.

1. "정점간의 간선은 두 집하장간에 화물 이동이 가능함" 이라는 뜻은 간선간의 방향성이 없이 양방향으로 이동 및 접근이 가능하다는 뜻이다.

2. "최단 경로" 해당 문제는 주어진 그림 및 1의 과정에서 그래프 문제 라는 것을 알 수 있다. 그래프 문제를 최단 경로로 풀어내는 알고리즘은 벨먼-포드 , 다익스트라, 플로이드 워셜 이다. (본인은 순수한 BFS를 통한 문제 해결방식은 간선간의 가중치가 존재하지 않을 때 주로 사용하므로 제외 하도록 하겠다.)

3. 주어진 N 즉, 정점의 개수는 최대 200이다. 플로이드 워셜의 시간복잡도는 0(n^3) 이기 때문에 200^3을 해도 시간 내에 통과할 것 같았다.

4. 단순히 최단 시간을 출력하는 것이 아닌 목적지에 도착하기 까지 거치는 첫번째 정점을 찾는 것 이다.

주어진 4가지의 핵심 단서를 통해서 플로이드 워셜을 사용, 최단 경로로 가중치가 갱신될 때 마다 첫번째 거쳐가는 정점 노드 값을 갱신 해주기로 했다.

💻 제출

📝 제출 코드

import java.io.*;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;


public class Main {
    static int N, M;
    static final int INF = 987654321; //충분히 큰 값
    static int[][] distance;
    static int[][] firstVisited;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        distance = new int[N + 1][N + 1];
        firstVisited = new int[N + 1][N + 1]; //첫 방문 배열

        //초기값 세팅 2 -> 1 정점의 첫 방문 정점은 1 이다.
        // i -> j = j
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                firstVisited[i][j] = j; 
            }
        }

        //충분히 큰값 INF 로 초기화
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i != j) {
                    distance[i][j] = INF;
                }
            }
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer stD = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(stD.nextToken()); //시작점
            int e = Integer.parseInt(stD.nextToken()); //목적지
            int v = Integer.parseInt(stD.nextToken()); //가중치 , 거리

            if (distance[s][e] > v) { //양방향 연결
                distance[s][e] = v;
                distance[e][s] = v;
            }
        }

        floyd(); //floyd warshall

        bw.write(print() + " ");

        bw.flush();
        bw.close();
        br.close();
    }

    static void floyd() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (distance[i][j] > distance[i][k] + distance[k][j]) {
                        //가중치 갱신
                        distance[i][j] = distance[i][k] + distance[k][j];

                        //거리 갱신 시에 첫번째 방문지 갱신
                        firstVisited[i][j] = firstVisited[i][k];
                    }
                }
            }
        }
    }

    static String print() {
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    sb.append("- ");
                } else {
                    sb.append(firstVisited[i][j] + " ");
                }
            }
            sb.append("\n");
        }

        return sb.toString();
    }

}

헥사고날 아키텍처, DDD 패턴을 참고하여 프로젝트를 진행했던 경험이 있다.

당시 기존의 MVC패턴에서 DDD패턴을 사용하자는 의견이 나와서 팀원들 전체가 시도 및 적용 했었는데 잘 알지 못하고 사용했던 것 같다.

아키텍처와 패턴을 완벽하게 구현하기란 참 어렵다는 것을 느꼈던 것 같다.

어쨌든 당시 DDD 장점은 "테스트 케이스에 무적이다." 라는 것이였는데 프로젝트의 일정에 쫒기던 상황이라 테스트 케이스를 작성하면서 진행하지 못했다.

프로젝트가 끝난 지도 3달 정도가 지난 지금 코테 문제 풀이에만 집중하다 보니 Spring Boot도 점점 가물가물하다.

Spring Boot의 예전 기억도 되찾을 겸 사용해 보지 못하고 넘어갔던 단위 테스트에 관해서 공부하면서 구현해 보겠다.

📗 단위 테스트?

특정 소스코드의 모듈이 의도한 대로 동작하는지 확인하고 싶을 때 사용한다.

단위 테스트는 개발자가 테스트하고 싶은 특정 부분만 독립적으로 테스트가 가능하기 때문에 코드를 리팩토링하거나 구현할 때 문제 여부를 빠르게 판단할 수 있다.

코드를 작성할 때 테스트 코드를 돌리면서 구현한다면 문제 발생 시 즉각적으로 조치가 가능할 것이다.

Spring에서의 단위 테스트는 Spring Container에 올라와 있는 Bean을 테스트하는 것이라고 한다.

📗 JUnit

JUnit이란 자바의 단위 테스트 프레임워크 이다.

SpringBoot 2.2.0 이전에는 JUnit4가 기본으로 설정되었지만, 2.2.0버전 부터는 JUnit5가 기본으로 설정 된다고 한다.

JUnit5는 런타임 시 Java8 이상을 요구하며, Gradle 4.7 이상이어야 한다. SpringBoot initializer에서 Spring-Web 의존성을 추가하면 자동적으로 추가 된다.

이미지 출처 : https://javacan.tistory.com/entry/JUnit-5-Intro

기존의 JUnit4는 하나의 jar파일로 의존성을 불러와서 다른 라이브러리를 참조해서 작동하는 방식이였는데 JUnit5 부터는 그 자체로 모듈화가 되어서 작동 된다.

🧩 JUnit Platform

테스트를 발견하고 테스트 계획을 생성하는 TestEngine 인터페이스를 정의 하며 TestEngine API를 제공한다. (테스트를 실행하는 런처 제공, TestEngine을 통해 테스트를 발견하고, 실행하고, 결과를 보고한다.)

🧩 Jupiter

JUnit5를 지원하는 TestEngine API 구현체 이다. 개발자가 JUnit5로 작성한 테스트의 경우는 Jupiter로 진행된다.

🧩 Vintage

JUnit4와 JUnit3을 지원하는 TestEngine의 구현이며 JUnit4와 JUnit3으로 작성된 테스트의 경우 Vintage로 진행된다.

📌 Annotations

🧩 Annotations -> @Test

//JUnit4
@Test(expected = Exception.class)
void create() throws Exception{
    //생략
}

//JUnit5
@Test
void create(){
    //생략
}

메서드가 테스트용 이라는 것을 나타내는 어노테이션 이다. 이전 JUnit4와 달리 속성을 선언하지 않는다.

🧩 Annotations -> LifeCycle

💡 JUnit 라이프 사이클 수행과정

• 기본적으로 위에서 아래로 @Test를 선언한 순서에 따라 수행이 된다.

1. @BeforeAll : JUnit 클래스가 수행되면 최초 한번 @BeforeAll 어노테이션을 선언한 메서드가 실행

2. @BeforeEach : @Test을 찾았다면 테스트 실행 전 @BeforeEach을 선언한 메서드가 실행

3. @Test : @Test를 선언한 메서드가 실행

4. @AfterEach : @Test 실행을 마치면 @AfterEach를 선언한 메서드가 실행

5. @Test를 선언한 메서드가 있는지 찾으며 존재하면 (2. 과정)을 반복수행하며, 존재하지 않는 경우 (6. 과정)을 수행

6. @AfterAll : 실행할 @Test가 존재하지 않는다면 @AfterAll을 선언한 메서드를 수행

7. 테스트를 종료합니다.

@BeforeAll : 해당 클래스에 위치한 모든 테스트 메서드 실행 전에 딱 한 번 실행되는 메서드

JUnit4의 @BeforeClass와 유사

@AfterAll : 해당 클래스에 위치한 모든 테스트 메서드 실행 전에 딱 한 번 실행되는 메서드

본 어노테이션을 붙인 메서드는 해당 테스트 클래스 내 테스트 메서드를 모두 실행시킨 후 딱 한번 수행되는 메서드다.

메서드 시그니쳐는 static 으로 선언해야한다.

@BeforeEach : 해당 클래스에 위치한 모든 테스트 메서드 실행 전에 실행되는 메서드 JUnit4의 @Before와 유사

@AfterEach : 해당 클래스에 위치한 모든 테스트 메서드 실행 후에 실행되는 메서드

JUnit4의 @After와 유사

매 테스트 메서드 마다 새로은 클래스를 생성하여 실행하기 때문에 효율적이지 못하다.

🤔 All, Each의 차이점

그렇다면 All 과 Each의 차이는 무엇일까?

@BeforeAll은 한 번만 실행되지만 @BeforeEach 매번 실행된다.

만약 특정 테스트를 실행했을 때 기존 조건들이 영향을 받아 이후 실행되는 테스트에 영향을 끼칠 우려가 있다면 매번 조건을 초기화해 주는 Each의 형태를 사용해 주는 것이 좋을 것이며 그렇지 않다면 All을 통해서 한 번만 작동하도록 하는 것이 좋을 것이다.

🧩 Annotations -> @Disabled

테스트를 하고 싶지 않은 클래스나 메서드에 적용하는 어노테이션 이다.

JUnit4의 @Ignore와 유사한 작동을 한다.

class JUnitExample{
    @Test
    @Disabled("Disabled")
    void disbaledTest(){
        //생략
    }

    @Test
    void test(){
        //생략
    }
}

🧩 Annotations -> @DisplayName

해당 테스트의 목적을 쉽게 표현할 수 있도록 해주는 어노테이션 이며 공백, Emoji, 특수문자 등을 지원한다.

@DisplayName("테스트 DisplayName")
class JUnitExample{
    @Test
    @DisplayName("DisplayName을 테스트 하기 위한 테스트")
    void test(){
        //생략
    }

}

🧩 Annotations -> @RepeatedTest

특정 테스트를 반복시키고 싶을 때 적용하는 어노테이션

반복적인 요청으로 성능을 측정할 때 활용한다면 좋을 것 같다.

반복 횟수와 반복 테스트 이름을 설정할 수 있다.

class JUnitExample{
    @RepeatedTest(10) //10번 반복 테스트
    @DisplayName("반복 테스트")
    void test(){
        //생략
    }
}

📌 Assertions

테스트 케이스의 수행 결과를 판별하는 메서드 이며 모든 Junit Jupiter Assertions는 static 메서드 이다.

🧩 Assertions -> assertThrows(expectedType,executable) 메서드

예외 발생을 확인하는 테스트 executable의 로직이 실행하는 도중 expectedType의 에러를 발생 시키는지 확인

//JUnit4
@Test(expected = Exception.class)
void test() throws Exception{
    //생략
}

기존의 JUnit4는 개발자가 직접 발생하는 예외 어노테이션에 기술하고 예외가 발생하는지 유무만 확인 할 수 있었다.

//JUnit5
@Test
void test() throws Exception{
    Exception e = assertThrows(Exception.class,() -> new Test(-1));
    assertDoesNotThrow(() -> System.out.println("Do Something"));
}

JUnit5의 assertThrows에서는 예외를 반환받아서 예외의 상태를 검증할 수 있다. 또한 해당 부분에서 예외가 발생하지 않았음을 검증하는 assertDoesNotThrow를 사용해서 추가적인 처리를 할 수 있게 되었다.

🧩 Assertions -> assertTimeout(duration,executable) 메서드

특정 시간 안에 실행이 완료되는지 확인 Duration : 원하는 시간 Executable : 테스트할 로직 인자로 원하는 시간과 테스트 로직을 받을 수 있다.

@Rule
public Timeout timeout = Timeout.seconds(5);

class TimeoutExample{
    @Test
    @DisplayName("타임 아웃 정상 통과 함수")
       void timeoutNotExceeded(){
        assertTimeout(ofMinutes(2), () -> Thread.sleep(10));
    }

    @Test
    @DisplayName("타임 아웃")
       void timeoutExceeded(){
        assertTimeout(ofMinutes(100), () -> Thread.sleep(100));
    }
}

🧣 Given-when-then 패턴

테스트 케이스를 구성할때 더 가독성 있고 유지보수하기 쉽게 구조화 하는 방법을 의미 한다.

테스트 케이스가 더 구체적이고 이해하기 쉬워지며 각각의 단계를 분리하여 각 테스트 부분이 어떤 역할을 담당하는지 명확해진다.

Given(설정) : 테스트의 초기 상태 또는 사전 조건을 설정. 입력 데이터나 테스트가 실행될 문맥을 지정

When(동작) : 테스트되는 동작 또는 이벤트를 설명하고 테스트되는 특정 메서드나 동작을 나타낸다.

Then(검증) : "When" 섹션에서 설명한 동작으로 인해 기대되는 결과 또는 동작을 정의

import org.junit.jupiter.api.Test;
import java.util.ArrayList;
import static org.junit.jupiter.api.Assertions.*;

class MyTest {

    @Test
    void testCode() {
        // Given
        ArrayList<String> list = new ArrayList<>();

        // When
        list.add("Apple");
        list.add("Banana");
        list.add("Grape");

        // Then
        assertEquals(3, list.size());
        assertTrue(list.contains("Apple"));
        assertFalse(list.isEmpty());
    }
}

참고

https://www.youtube.com/watch?v=EwI3E9Natcw&t=99s

https://adjh54.tistory.com/342#google_vignette

JWK(Json Web Key)는 JSON을 형태로 암호화키를 나타내는 데이터 구조 이다.

JWK를 공부하던 도중 문득 기존 개념인 대칭키와 비대칭키에 대해서 한번 더 정리 해보자는 생각이 들었다.

🔑 대칭키

A가 B에게 전달할 문서가 존재하고 문서 자체로 B에게 전달하는 방식을 사용한다고 가정해보자.

문서에 어떠한 조치도 하지않고 B에게 전달하기 때문에 중간에 악성 유저가 문서를 탈취 또는 열람 한다면 이후 상황에 악 영향을 끼칠 것 이다.

애초에 탈취 당하지 않는다면 좋겠지만 탈취 당하더라도 악성유저가 문서를 열람하지 못했으면 하는 바람이 생긴다.

이때 문서를 암호화 해서 전달 하는 방식이 바로 대칭키 방식이며 하나의 Key로 문서를 암호화 해서 전달하기 때문에 해당 키의 소유자가 아니라면 문서를 복호화 할 수 없다.

하지만 여기서도 이상한 부분이 존재한다.

문서를 암,복호화 할때 동일한 Key를 사용하기 때문에 A가 문서를 암호화 해서 전달한다면 B가 복호화 하기 위해 Key를 보유 해야한다.

A가 문서를 암,복호화할 Key를 가지고 있다면 B에게 Key를 전달하는 과정이 필요할 것이다.

Key를 전달하는 과정에서 악성유저가 열람 또는 탈취 한다면 B에 Key가 전달 되더라도 문제가 발생한다.

문서가 암호화 되어 전달하더라도 악성유저의 입장에서는 암호화 된 문서를 복호화 할 수 있기에 문제없이 열람이 가능하다.

위와 같은 상황 때문에 문제는 원점으로 다시 되돌아간다.

🔑 비대칭키

문서는 암호화 하여 전달할 수 있지만 Key를 전달하는 과정에서 안정성을 보장받지 못하는 대칭키의 문제점을 살펴보았다.

비대칭키 방식은 각 사용자들이 각자의 암,복호화 키를 따로 가지는 것이다.

각 사용자들은 암호화 할수 있는 Key를 모두가 사용할 수 있도록 공개해 버린다.

그렇다면 A가 B에게 전달한 문서가 있을때 어떻게 해야할까?

A는 B가 공개해놓은 B의 Encrypt용 공개키로 전달한 자신의 문서를 암호화 한다.

B의 공개키로 암호화된 A의 문서는 B의 Decrypt Key 즉 복호화 Key가 아니라면 복호화가 불가능 하다.

B의 공개키로 암호화된 문서는 탈취 당하더라도 악성유저가 B의 복호화 키는 알 수 없기에 문서내용은 알 수 없다.

대칭키와 달리 문서를 암호화 할 key를 개인이 소유하고 전달 필요가 없기에 탈취당할 위험이 적다.

🔑 JWK (Json Web Key)

암호화 키를 표현하기 위한 JSON 객체에 관한 표준이다.

대칭키 또는 비대칭키를 JSON의 형태로 표현하는 방식이며 작동원리 자체는 동일하다.

JWT를 생성하거나 검증하는데 사용되는 공개키 또는 비공개 키를 JWK화 해서 사용할 수 있다.

Key에 JWK를 적용하여 사용할 경우 Public으로 공개되는 Encrypt 용 Key를 JSON 형태로 배포 한다면 JWK라고 명칭할 수 있는 것이다.

{
  "keys": [
    {
      "alg": "RS256",         // 알고리즘 종류 (예: RS256)
      "e": "AQAB",            // RSA public exponent
      "kid": "2011-04-29",    // Key ID
      "kty": "RSA",           // Key Type (RSA)
      "n": "0vx7agoebGcQSuuPiLJXZptN27ctQ...", // RSA modulus
      "use": "sig"            // Public Key Use (예: "sig" -> signature, "enc" -> encryption)
    }
  ]
}

🤔 정리

JWK에 대해서 간략하게 알아보았다.

이 외에도 JWK 관련 지식들에 대해 공부 하고 구현 하기 위해 여러가지 생각을 개인적으로 진행 한 후Spring boot에서 아래와 같은 상황을 구현 할 것이다.

상황은 비대칭키 작동방식을 사용한다고 가정한다.

예전 프로젝트와 연관지어서 JWK로 공개키를 표현하고 JWK로 데이터를 암호화 한다음 서버로 전달 해보자. (Client)

암호화된 데이터를 전달받은 서버에서는 개인 키로 암호화된 문서를 복호화 해서 사용해보자. (Server)

📌 입력

📌 출력

💻 제출

🤔 생각

처음에는 주어진 N의 값이 200 이하 이기 때문에 floyd로 풀려고 접근 했었다. floyd 알고리즘은 시간복잡도가 O(n^3)이기 때문에 정점의 개수 N이 작다면 시도 해볼만 하다고 생각했다.

하지만 이번문제에서는 상하좌우 로만 이동이 가능하다는 조건이 있었기에 단순히 3중 반복문을 통해서 전체 순회를 하는 floyd를 억지로 넣으려고 하는 순간 문제 난이도가 올라갈 것 이라는 생각이 들었다.

그렇다면 남은 최단거리 알고리즘은 다익스트라, 벨먼-포드 알고리즘 인데 벨먼-포드는 현재 학습하지 않은 상태였다.

선택지가 없기에 다익스트라로 풀기 시작했다.

cost를 작은 순으로 계산해야하기 때문에 우선순위 큐를 적용 했으며 기존의 데이터를 담고 있는 2차원 배열은 그대로 두고 임시 배열을 하나 생성 해서 거리계산을 통해 갱신 하기로 했다.

📝 제출 코드

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {
    static int N;
    static int[][] map;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] dx = {0, 0, 1, -1}; //동 서 남 북
    static int[] dy = {1, -1, 0, 0}; //동 서 남 북
    static final int INF = 987654321; //충분히 큰값

    static class Node {
        int x;
        int y;
        int cost;

        public Node(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }

    public static void main(String[] args) throws IOException {
        int roop = 1;
        while (true) {
            N = Integer.parseInt(br.readLine());

            if (N == 0) break; //입력값이 0이면 입력이 존재하지 않음

            map = new int[N][N];

            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            bw.write("Problem " + roop + ": " + dijkstra() + "\n");

            roop++;
        }

        bw.flush();
        br.close();
        bw.close();
    }

    static int dijkstra() {
        //cost 에 따른 우선순위 데이터 출력
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (a, b) -> Integer.compare(a.cost, b.cost)
        );


        //총 거리계산을 위한 임시 배열 생성 및 초기화
        int[][] move = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(move[i], INF);
        }

        //첫번째 시작 위치 입력
        pq.offer(new Node(0, 0, map[0][0]));
        move[0][0] = map[0][0];


        while (!pq.isEmpty()) {
            Node now = pq.poll();

            if (now.x == N - 1 && now.y == N - 1) {
                //최종 목적지 도착
                return now.cost;
            }

            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if (range(nx, ny)) {
                    //거리값 비교하여 갱신
                    if (move[nx][ny] > move[now.x][now.y] + map[nx][ny]){
                        move[nx][ny] = move[now.x][now.y] + map[nx][ny];
                        pq.offer(new Node(nx,ny,move[nx][ny]));
                    }
                }
            }
        }

        //최종 목적지 찾기 실패
        return -1;
    }

    //배열 범위 안에서 작동하는지 검증
    static boolean range(int nx, int ny) {
        return 0 <= nx && nx < N && 0 <= ny && ny < N;
    }

}

📌 입력

📌 출력

🤔 문제풀이

해당 문제를 읽었을때 다양한 풀이 방법을 생각했었다.

문제를 해결하기 위해서는 cycle에 들어가지 않는 즉 포함되지 않고 존재하는 정점들의 수를 반환 해주면 된다.

1. DFS를 통해 시작점으로 돌아오는지 전체 탐색

하지만 정점의 개수 N 범위가 굉장히 컷다.

모든 정점을 탐색해서 처음 시작점으로 돌아오는지 확인 해야하기 때문에 시간을 줄이려는 노력이 필요했다.

정점 탐색을 줄이기 위해 한번 발견한 cycle은 따로 DP로 저장해놓고 탐색을 하지 않고 결과를 반환 하는 방법을 고려했다.

하지만 DP로 줄일 수 있는 상황 즉 cycle이 존재하지 않는다면 결국 모든 정점을 탐색 해야하기 때문에 의미가 퇴색 된다고 생각했다.

2. 위상정렬을 통해서 cycle이 발생하는지 확인 하기

정방향

위 그림처럼 그래프가 구현된다고 생각 해보자. 해당 그래프처럼 구현이 된다면 기존 위상정렬 방식으로는 indegree가 0인 1부터 Queue에 삽입 될 것이다.

Queue의 data를 poll하면서 로직을 이어 간다면 cycle이 있는지 여부는 확인 할 수 있을 것이다.

     for (int next : relation[cur]){
                inDegree[next]--;

                if (inDegree[next] == 0){
                    q.offer(next);
                    ans++;
                }
            }

선행 되어야 할 정점과 연결되어 있는 모든 정점을 탐색하기에 cycle에 속하지 않는 4, 6 역시 cycle을 판단할때 포함되어서 같이 진행 되므로 따로 분류하기가 껄끄러웠다.

cycle에 포함되지 않는 정점들은 로직에서 완전히 분리하고 싶었다.

역방향

그래프의 간선을 역으로 뒤집는다면 indegree가 0인 차수는 1이 아닌 4, 6으로 시작 한다.

indegree가 0인 4, 6을 Queue에 삽입하고 진행을 하면 이후 어떤 정점도 indegree가 0이 되지 못한다.

indegree가 0이되는 노드들은 cycle에 포함되지 않는 정점이 다.

하나의 예시로는 이해가 힘드니 하나 더 생각 해보자.

그래프는 이미 간선이 뒤집힌 경우라고 가정한다.

indegree가 0인 정점은 4, 5, 6, 9이다.

indegree가 0인 정점을 위상정렬을 통해 탐색할때 indegree가 0이되는 정점은 3, 6, 7 이다.

3, 6, 7 정점은 Queue에 삽입 될 것이며 다음 정점의 indegree를 줄여 갈 것이다.

위와 같이 연결된 정점을 계속 반복해서 탐색한다면 모든 정점이 탐색되는 것을 알 수 있다.

위 예제의 그래프는 모든 정점이 탐색되기 때문에 cycle이 없다고 판단이 가능하다.

💻 제출

📝 제출 코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    static int N, M;
    static ArrayList<Integer>[] relation;
    static int[] inDegree;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        N = Integer.parseInt(st.nextToken()); //부원의 수
        M = Integer.parseInt(st.nextToken()); //관계의 수

        relation = new ArrayList[N+1];

        for (int i=1; i<=N; i++){
            relation[i] = new ArrayList<>();
        }

        inDegree = new int[N+1];

        for (int i=1; i<=M; i++){
            StringTokenizer stD = new StringTokenizer(br.readLine()," ");
            int s = Integer.parseInt(stD.nextToken());
            int e = Integer.parseInt(stD.nextToken());

            //역방향 연결, 그래프를 뒤집는 로직
            relation[e].add(s);
            inDegree[s]++;
        }

        bw.write(topologicalSort() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    static int topologicalSort(){
        Queue<Integer> q = new LinkedList<>();
        for (int i=1; i<=N; i++){
            if (inDegree[i] == 0){
                q.offer(i);
            }
        }

        int ans = q.size(); //queue에 삽입된 초기 개수는 cycle에 속하지 않는 정점


        while (!q.isEmpty()){
            Integer cur = q.peek();
            q.poll();

            for (int next : relation[cur]){
                inDegree[next]--;

                if (inDegree[next] == 0){
                    q.offer(next);
                    //indegree가 0인 정점은 cycle이 아니다.
                    ans++;
                }
            }
        }

        return ans;
    }
}

📗 문제를 풀며...

두달 조금 넘는 시간을 백준 문제만 300개 넘게 풀어왔다. 백준 문제를 풀면서 항상 느끼는 불편한 점은 코드를 제출 했을때 체크하는 테스트케이스 반례에 비해 제공되는 반례가 너무나도 적다는 것이다.

물론 완벽한 코드를 제출하기 바랬으면 하는 의도가 있다면 모르겠지만 코딩테스트를 "연습"하는 공간이기에 반례를 넉넉히 문제에 제공해준다면 쓸데없는 삽질을 덜 하지 않을까 하는 개인적인 생각이 있다.

백준에 많은 문제가 있어서 주로 사용하지만 이후 조금 더 숙련도가 쌓인다면 리트코드, 코드포스 등등 다양하게 경험 하는게 효과적일 것 같다.

📌 입력

📌 출력

💻 제출

🤔 문제 풀이 까지의 생각

일단 정점과 연결선을 통해서 푸는 그래프 문제들은 다양한 풀이방법이 많다. 그중 최단 거리와 같은 키워드가 존재 하는 경우는 bfs, 다익스트라, 플로이드 등등 을 첫번째로 생각한다.

이번 문제는 최단거리 문제가 아니기에 제외 했으며 N의 수가 굉장히 낮아 플로이드 적용이 가능하지 않나..? 라고 생각을 했다. (floyd warshall은 3중 for문이 필요하기 때문에 시간 복잡도 효율이 매우 안좋다.)

플로이드 문제를 풀때는 항상 연결선 간의 비용이 주어지지만 이번문제의 경우에는 주어지지 않았다.

로직을 돌릴때 확장 할 비용을 연결선 간의 거리 계산이 아니라 양방향 추가 개수 즉 cnt를 저장하기 위한 목적으로 사용한다면 어떨까 하는 생각이 들었다.

예제 데이터를 적용한 정점과 연결선의 관계는 위 이미지와 같을 것 이다.

양방향 연결을 통해서 접근이 가능 한 경우 cnt가 1이 되도록 설정 해주었다. (s,e 연결이 되도록 예제가 주어졌다면 반대 방향인 e,s의 cnt를 1 추가)

floyd를 통해서 확장을 해준다면 정점 부터 정점 까지 이동하기 위한 모든 양방향 cnt 개수가 정리 될 것 이다.

📝 코드

import java.io.*;
import java.util.StringTokenizer;


public class Main {
    static int N, M,Q;
    static final int INF = 987654321;
    static int[][] distance;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        N = Integer.parseInt(st.nextToken()); //건물 수
        M = Integer.parseInt(st.nextToken()); //관계 선

        distance = new int[N+1][N+1];

        for (int i=1; i<=N; i++){
            for (int j=1; j<=N; j++){
                if (i != j){
                    distance[i][j] = INF;
                }
            }
        }

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

            int s = Integer.parseInt(stD.nextToken());
            int e = Integer.parseInt(stD.nextToken());
            int rotate = Integer.parseInt(stD.nextToken());


            if (distance[s][e] > 1){
                distance[s][e] = 0;
            }

            distance[e][s] = (rotate == 0) ? 1 : 0;
        }

        floyd();

        Q = Integer.parseInt(br.readLine());

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

            int s = Integer.parseInt(stD.nextToken());
            int e = Integer.parseInt(stD.nextToken());

            bw.write(distance[s][e] + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }



    static void floyd(){
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {

                    if (distance[i][j] > distance[i][k] + distance[k][j]){
                        distance[i][j] = distance[i][k] + distance[k][j];
                    }
                }
            }
        }
    }
}

📌 입력

📌 출력

💻 제출

🤔 문제 해결까지의 생각

입력 예제

2
goredrinker galeforce
riftmaker everfrost

각 아이템의 순서가 일부만 정해져 있으므로 전체의 순서를 한번에 알 수는 없다.

일부만 순서가 주어지는 경우에는 위상 정렬 풀이를 제일 먼저 생각할 수 있다.

해당 예제 값의 prev item 과 next item을 연결 하면 위와 같은 이미지 처럼 연결 되며 indegree는 해당 아이템을 사기 위한 이전 템들의 개수 이다.

indegree 값이 0인 item들은 먼저 제작해야 할 item이 존재 하지 않으므로 큐에 삽입이 된다.

데이터를 삽입하기 전에는 사전 순으로 데이터를 정렬해야 하고 정렬 된 데이터들은 큐에 삽입한다.

삽입된 큐의 데이터들은 위상정렬 로직을 거치면서 차수를 줄여가면 사전 순으로 출력이 될 것 이라고 생각 했다.

📝 제출 코드

import java.io.*;
import java.util.*;


public class Main {
    static int N;
    static Map<String, ArrayList<String>> relation = new HashMap<>();
    static Map<String, Integer> inDegree = new HashMap<>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        N = Integer.parseInt(br.readLine()); //아이템 수

        for (int i = 0; i < N; i++) {
            StringTokenizer stD = new StringTokenizer(br.readLine(), " ");

            String prev = stD.nextToken();
            String next = stD.nextToken();

            if (relation.get(prev) == null) {
                relation.put(prev, new ArrayList<>());
                inDegree.put(prev, 0);
            }

            if (inDegree.get(next) == null) {
                relation.put(next, new ArrayList<>());
                inDegree.put(next, 0);
            }

            relation.get(prev).add(next);
            inDegree.put(next, inDegree.get(next) + 1);
        }

        solution();

        boolean flag = true;
        for (String key : inDegree.keySet()){
            if (inDegree.get(key) != 0){
                flag = false;
                break;
            }
        }

        bw.write(flag == true ? sb.toString() + " " : "-1\n");
        bw.flush();
        bw.close();
    }

    static void solution() {
        Queue<String> q = new LinkedList<>();

        ArrayList<String> inDegreeZero = new ArrayList<>();

        for (String key : inDegree.keySet()) {
            if (inDegree.get(key) == 0) { //차수가 0
                inDegreeZero.add(key);
            }
        }

        Collections.sort(inDegreeZero); //사전 정렬

        for (String key : inDegreeZero){ //사전 정렬 된 단어 삽입
            q.offer(key);
        }

        while (!q.isEmpty()){
            int size = q.size();

            ArrayList<String> sortStr = new ArrayList<>();
            for (int i=0; i<size; i++){
                String now = q.poll();
                sb.append(now + "\n");

                for (String next : relation.get(now)){
                    inDegree.put(next , inDegree.get(next) - 1); //차수 감소

                    if (inDegree.get(next) == 0){
                        sortStr.add(next);
                    }
                }
            }

            Collections.sort(sortStr);

            for (String data : sortStr){
                q.offer(data);
            }
        }
    }
}

무지는 죄 다. 알아가보도록 하자.

📗 Java String

📌 String

먼저 String 은 immutable(불변) 하다.

처음 String 형태로 문자열을 생성할때 힙 영역에 해당 문자열 만큼의 메모리 공간이 할당 되는데 이 할당된 공간은 수정되어도 변하지 않는다.

따라서 기존의 String 을 변하게 할 경우 이미 할당된 공간을 GC가 회수 하고 수정된 String 만큼을 재 할당 하여 저장 한다.

코딩 테스트를 준비 하다보면 문자열을 자르고 연결하는 작업이 생각보다 잦은데 이때 String을 사용한다면 성능이 많이 떨어지기때문에 StringBuilder 또는 StringBuffer를 주로 사용하게 된다.

물론 String 을 한번 할당 후 수정사항이 많지 않으면 간단하게 사용이 가능하기 때문에 나쁘지 않으면 동기화에 대해 신경쓰지 않아도 되기때문에(Thread-safe), 내부 데이터를 자유롭게 공유 가능하다.

📌 Thread Safe

Thread Safe 란 공유 자원에 동시에 다수의 스레드가 접근 하더라도 값이 변경되지 않는 일관적인 결과를 반환 하는 것을 뜻한다.

📗 StringBuilder / StringBuffer

StringBuilder 과 StringBuffer 는 String과는 달리 기존에 할당 한 메모리 공간을 필요에 따라 확장하며 가변(mutable)적인 특성을 가진다.

StringBuilder과 StringBuffer의 차이는 Multi Thread에서 안전 여부에 따라 나뉘게 되는데 StringBuilder 는 thread 에서 안전하지 않고 StringBuffer는 thread에서 안전하다.

StringBuilder는 동기화를 지원하지 않는 반면, StringBuffer는 synchronized 키워드를 사용, 동기화를 지원하여 멀티 스레드 환경에서도 안전하게 동작할 수 있다.

📌 java synchronized

java에서 synchronized 키워드는 여러개의 스레드가 한 개의 자원에 접근할려고 할 때, 현재 데이터를 사용하고 있는 스레드를 제외하고 나머지 스레드들이 데이터에 접근할 수 없도록 막는 역할을 수행한다.

📗 접근 제어자

Private

public class Sample {
    private String secret;
    private String getSecret() {
        return this.secret;
    }
}

private 즉 외부에서는 간섭 할 수 없다. 접근 제어자가 private으로 설정되었다면 private이 붙은 변수나 메서드는 해당 클래스 안에서만 접근이 가능하다.

secret 변수와 getSecret 메서드는 오직 Sample 클래스에서만 접근이 가능하고 다른 클래스에서는 접근이 불가능하다.

private로 선언한 변수는 외부에서 직접적인 변경이 불가능 하기 때문에 getter를 통해서 값을 읽어오고 setter를 통해서 값을 변경 한다.

외부에서 secret변수에 직접 값을 넣어 대입 할 경우 어떤 문제가 발생 할 지 파악하기 난해 하기 때문에 본인은 private로 작성하는 것을 선호한다.

📗 Default

접근 제어자를 별도로 설정하지 않는다면 변수나 메서드는 default 접근 제어자가 자동으로 설정되어 동일한 패키지 안에서만 접근이 가능하다.

package house;  // 패키지가 동일하다.

public class HouseKim {
    String lastname = "kim";  // lastname은 default 접근제어자로 설정된다.
}

package house;  // 패키지가 동일하다.

public class HousePark {
    String lastname = "park";

    public static void main(String[] args) {
        HouseKim kim = new HouseKim();
        System.out.println(kim.lastname);  // HouseKim 클래스의 lastname 변수를 사용할 수 있다.
    }
}

📗 Protected

접근 제어자가 protected로 설정되었다면 protected가 붙은 변수나 메서드는 동일 패키지의 클래스 또는 해당 클래스를 상속받은 클래스에서만 접근이 가능하다.

package house;  // house 패키지

public class HousePark {
    protected String lastname = "park";
}

package house.person;  // house.person 패키지

import house.HousePark;

public class EungYongPark extends HousePark {  // HousePark을 상속했다.
    public static void main(String[] args) {
        EungYongPark eyp = new EungYongPark();
        System.out.println(eyp.lastname);  // 상속한 클래스의 protected 변수는 접근이 가능하다.
    }
}

📗 Public

접근 제어자가 public으로 설정되었다면 public 접근 제어자가 붙은 변수나 메서드는 어떤 클래스에서도 접근이 가능하다.

package house;

public class HousePark {
    protected String lastname = "park";
    public String info = "this is public message.";
}

import house.HousePark;

public class Sample {
    public static void main(String[] args) {
        HousePark housePark = new HousePark();
        System.out.println(housePark.info);
    }
}

public 에서 변수를 선언하면 외부에서 직접 값을 대입하여 변경 할 수 있기에 편리하다고 생각 할 수 있다. 하지만 개발자 혹은 다른 실수로 인해 뜻하지 않는 변수 값을 변경 할 경우 예상하지 못하는 오류가 연쇄적으로 발생할 수 있을 것 이다.

📗 캡슐화와 은닉화의 차이

📌 캡슐화

예를 들어 감기약을 먹는다고 가정했을때 감기약을 복용하려는 사람은 말 그대로 "감기약"에 집중 할 것이다.

감기라는 병에 걸렸으니 감기약을 먹는 것이고 일반적으로 감기약 알약에 들어있는 수많은 성분들이 어떤 작용을 하는지 생각하고 먹지는 않을 것 이다.

이것을 바꿔서 생각해보면 사용자는 해당 객체(감기약)에서 제공하는 연산들을 통해서 객체를 제어 할 것이고 객체 내부의 연산을 사용하기 때문에 외부의 접근 제한하고 작동 할 수 있다.

외부의 접근을 제한하게 된다면 결합도가 떨어질 것이고 객체 자체의 응집도는 증가 할 것이다.

외부의 잘못된 접근으로 값이 변하는 의도치 않는 동작을 방지하는 보호 효과도 누릴 수 있다.

public class Phill {
    private int id;
    private String name;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

본인은 외부의 접근을 제한 하기 위해서는 Java 기준, 접근 제어자를 통해서 private로 설정후 getter 또는 setter를 통해서 객체를 조작한다.

📌 은닉화

위에 언급했던 캡슐화와 혼동 할 수 있는데 본인은 은닉화가 캡슐화 보다 더 큰 개념이라고 생각하고 있다.

정보 은닉 이라는 단어를 보자면 무언가 정보를 은닉하여 보안적인 효과를 얻는 것 같다. 그러나 보안적인 측면 뿐만 아니라, 은닉되어 알필요가 없어 덜 알아도 되어 간편하게 사용할 수 있게 해주는 의미도 내포한다.

대표적으로 은닉화는 3가지로 분류할 수 있다고 생각한다.

• 객체의 구체적인 타입 은닉 (업캐스팅)
• 객체의 필드 및 메소드 은닉 (캡슐화)
• 구현 은닉 (인터페이스 & 추상 클래스)

📌업캐스팅(Upcasting)

구체적인 자식객체의 정보를 은닉하는 upcasting 도 정보은닉의 일종이다.

 class Car{
    public void call(){ 
        System.out.println("car"); 
    }
}

class Myclass {
    // 생략
    public void method() {
        Car car = new Car(); // Car 객체 생성

        car.call(); // Myclass 클래스는 Car 클래스에 의존적인 코드
    }
}

만약 Car 과 거의 동일하게 작동하는 객체인 Bike로 코드를 수정 한다고 생각해보자. Bike로 수정하기 위해서는 상당한 코드를 수정 해줘야 한다.

하지만 여러가지 의 타입을 통합하기 위해 추상클래스로 상위 객체를 만들어 다형성 형태를 만들어 준다면 생성 부분만 수정함으로써 원하는 작동을 만들어 낼 것 이다.

abstract class Car{
    abstract public void call(); 
}

class Bike extends Car{
    public void call(){ 
        System.out.println("bike"); 
    }
}

class Myclass {
    // 생략
    public void method() {
        Car car = new Bike(); // Bike 객체 생성

           car.call(); 
    }
}

객체를 생성 후 call 함수를 호출 하더라도 Bike 의 call 함수를 직접적으로 호출하지 않았기 때문에 일종의 정보 은닉 중 하나라고 볼 수 있을 것이다.

📌구현 은닉(Interface)

java 에서는 클래스와 유사하게 상속 가능한 타입이면서 구체적인 구현을 배제한 인터페이스를 만들어 메소드 추상화를 통해 상속시킬 공개 메서드를 통합적으로 관리 한다.

interface InterProcess {
    public void work(); // 추상 메소드
}

class Process implements InterProcess {
    private void init(){} // 은닉 메서드
    private void process(){} // 은닉 메서드
    private void release(){} // 은닉 메서드

    public void work(){ // 공개 메서드 + 메소드 구체화
        init(); 
        process();
        release();
    }
}

public class Main {
    public static void main(String[] args) {
        InterProcess c = new Process(); // 상위 클래스 타입 처럼 이용될 수 있다
        c.work();
    }
}

캡슐화를 통해 최소한으로 줄인 공개 메서드를 인터페이스의 추상 메소드와 연동이 되면서, Process 클래스의 기능 동작을 하는데 있어 업캐스팅으로 인한 멤버 제한과 같은 제한 요소는 없어진다.

이밖에 인터페이스를 이용하면 실질적 클래스 간의 의존 관계가 없어지면서 기능 확장에 있어 제약이 줄어들게 된다.

📗 인터페이스와 추상클래스

📌 abstract

먼저 상위 클래스와 추상 클래스는 똑같이 extends로 확장이 가능 하지만 추상 클래스는 객체 생성이 불가능 하고 하위 클래스에 메서드 작성을 강제 할 수 있다.

추상 메서드는 메서드의 선언부만 존재하고 구현코드가 존재하지 않는다.

구현부가 없는 메서드를 단 하나라도 가진 클래스는 추상 클래스가 되며 추상 클래스가 되면 new 키워드를 사용하여 인스턴스화 할 수 없다. 즉, 클래스를 쓸 수 없게 되는 것 이다.

추상클래스를 사용하려면 다른 클래스가 추상 클래스를 상속받아야 하는데 상속받은 자식 클래스가 부모 클래스에 존재하는 모든 추상메서드를 오버라이딩 하여 구현부를 설계하면 비로소 사용할 수 있는 객체가 된다.

public abstract class Human{
    String name;

    Human(String name){
        this.name = name;
    }

    void show(){}; // 하위클래스에 메서드 작성(Override)을 강제
} 

📌 Interface

인터페이스는 추상 클래스의 특수형태 이며 추상클래스 중에서 멤버 변수와 메서드를 제거한 채 추상 메서드만을 남긴 형태이다. (변하지 않는 고정값인 상수는 선언 할 수 있다.)

인터페이스도 추상 클래스와 마찬가지로 구현한 자식 클래스에서 인터페이스의 추상 메서드를 모두 오버라이딩 해야지만 비로서 객체를 사용할 수 있다. (추상클래스나 인터페이스를 구현한 자식 객체가 추상 메서드를 전부 구현하지 않았다면 컴파일이 불가)

메서드를 직접 작성하지 않고 정의만 내리기 때문에 다중 상속에서 발생하는 메서드간의 충돌을 걱정 할 필요가 없다.

public interface class Human{
    final String name; // 필드값 선언 불가 , 상수만 선언이 가능

    void show(); //메소드 이름 선언 , body 내용을 작성 할 수 없다.
} 

📌 차이점

그렇다면 abstract와 interface에 대해서 굉장히 비슷하게 생각이 될 것이다.

목적에 따른 분류가 가능하며 추상 클래스는 상속받은 하위 클래스들이 exteds 즉 확장의 느낌이 강하고 인터페이스는 implements 즉 기능 구현의 느낌이 강하다.

추상 클래스는 자신의 기능들을 하위로 확장 시키는 것이 주목적이며 인터페이스는 자신에게 정의된 메서드를 각 클래스의 목적에 맞게 동일한 기능으로 구현 하는 것 이다.

📗 객체지향 의 4가지 특성

📌 상속

상위 클래스의 특성을 하위 클래스가 물려 받는 것을 뜻하며 추상화 와 상속은 상호 보완적인 관계이다.

상위 클래스에서 이미 정의 된 클래스를 재사용해서 만들 수 있기 때문에 효율적이고, 개발 시간을 줄여주게 된다.

상위 클래스에서 private로 접근 제어자가 지정 되어있다면 하위 클래스에는 상속되지 않는다.

📌 다형성

다형성이란 여러 개를 의미하는 poly와 형태 또는 실체를 의미하는 morphism의 결합어로, 하나의 객체가 여러 가지 형태를 가질 수 있는 것을 의미한다.

📌 캡슐화

연관된 데이터(변수)와 기능(메소드)을 하나로 묶고, 불필요한 요소를 외부에 노출되지 않도록 설계하는 방식을 뜻한다. 자바에서는 접근 제어자(public, private, default, protected)를 통해 캡슐화를 구현할 수 있다.

위에서 한번 언급 했으므로 크게 짚고 넘어가지는 않겠다.

📌 추상화

어떤 객체가 존재 할 때 객체를 추상화 할 수록 객체는 자신만의 특성을 잃어버리고 공통적인 특성만 존재 하게 된다.

예를 들어 비글 이라는 강아지가 존재한다고 생각 해보자.

비글을 추상화 하면 강아지로 추상화 될 것이다. 강아지로 추상화가 된다면 비글의 본연적인 특성은 사라지고 모든 강아지가 가지고 있는 공통적인 특성만 남게 될 것이다.

강아지를 한번 더 추상화 해서 동물로 정의 한다고 가정해보자. 강아지가 가지고 있는 고유한 특성들은 사라질 것 이고 동물이 가지고 있는 공통적인 특성만 가지고 있는 객체로 정의할 수 있을 것이다.

📗 객체지향 설계 5원칙

📌 단일 책임 원칙(SRP, Single Responsibility Principle):

클래스는 하나의 기능만을 위해 작동해야 한다.

📌 개방-폐쇄 원칙(OCP, Open-Closed Principle)

확장은 자유롭게 이루어져야 하지만, 기존 코드의 수정은 지양해야 한다는 원칙.

📌 리스코프 치환 원칙(LSP, Liskov Substitution Principle)

하위 클래스는 상위 클래스를 대체할 수 있어야 한다는 원칙. 하위 클래스는 상위 클래스의 기능을 모두 사용할 수 있어야 하며, 추가적인 기능도 사용 가능해야 한다.

📌 인터페이스 분리 원칙(ISP, Interface Segregation Principle)

하나의 큰 인터페이스보다는 기능별로 분리된 여러 개의 인터페이스를 사용하는 것이 좋다는 원칙.

📌 의존성 역전 원칙(DIP, Dependency Inversion Principle)

객체 간 의존성을 내부에서 주입하는 것보다 외부에서 주입하는 것이 좋다는 원칙. 이를 통해 각 객체의 응집도를 높이고 결합도를 낮출 수 있다.

📗 Class, Object, Instance

📌 Class

간단히 말해서 객체를 생성하기 위한 설계 틀 같은 것이다.

예를 들어 붕어빵을 만들어 내려할때 매번 붕어빵을 반죽해서 만드는 것 보다 붕어빵 틀에 재료를 부어서 원할때 마다 찍어내는 것이 훨씬 효율적 이고 간편할 것 이다.

public class FishBread{
    int price;
    String dough;
    String ingredients;

    public FishBread(int price, String dough, String ingredients){
        //생략
    }
    //생략
}

📌 Object

위에서 생성한 FishBread를 Class로 정의 했다면 FishBread 를 변수로 선언 하는 것이 Object 즉 객체 라고 한다.

    public static void main(String[] args) throws IOException {
        FishBread fb;
    }

📌 Instance

변수를 선언한 FishBread를 실사용 할 수 있도록 실체화 하는 것을 인스턴스 라고 한다.

    public static void main(String[] args) throws IOException {
        FishBread fb = new FishBread(10000, "밀가루", "팥");
    }

참고

https://inpa.tistory.com/entry/JAVA-☕-String-StringBuffer-StringBuilder-차이점-성능-비교

https://inpa.tistory.com/entry/OOP-%EC%BA%A1%EC%8A%90%ED%99%94Encapsulation-%EC%A0%95%EB%B3%B4-%EC%9D%80%EB%8B%89%EC%9D%98-%EC%99%84%EB%B2%BD-%EC%9D%B4%ED%95%B4

이번 글에서는 점점 사라지고있는 spring 및 java에 관련 된 cs에 대해서 작게나마 정리 해 보겠다.

🤔 Spring 이란?

엔터프라이즈용 Java 애플리케이션 개발을 편하게 할 수 있게 해주는 오픈소스 경량급 애플리케이션 프레임워크 이다.

결국 Java 기반으로 애플리케이션 을 개발하기 위한 프로그래밍 기술의 집합, 애플리케이션을 개발하기 위해서는 많은 코드들과 기술이 필요한데 이런 대중적인 기술들을 더 쉽게 사용할 수 있도록 제공 해주는 오픈소스 프레임 워크 인 것 이다.

spring 을 사용할 때 적용시킬 기술들을 선택해서 사용 할 수 있으며 다양한 기술의 버전이 충돌 함에 따라 얻는 문제점들은 spring boot 에서 자동적으로 버전 관리를 함으로써 해결 된다.

설정 문제를 boot에서 간단히 해결 할 수 있기 때문에 개발자는 비지니스 로직을 구현하는데 더 집중 할 수 있다.

📚 Spring 특징

📗 POJO(Plain Old Java Object)

위 이미지는 IoC/DI, AOP, PSA를 통해 POJO를 만족할 수 있다는 것을 의미 한다.

Plain Old Java Object는 순수하게 java로 설계됨으로써 java의 특성인 객체 지향을 만족하면서 필요에 따라 재활용 될 수 있어야 한다.

POJO에 애플리케이션의 핵심 로직과 기능을 담아서 설계하고 개발하는 방식을 POJO 프로그래밍 이라고 한다.

만약 순수 java에서 제공하는 기술이 아닌 외부 기술을 적용하여 로직을 작성할 경우 추후 해당 기술이 신기술로 교체되거나 더이상 지원되지 않음에 따라 변경이 필요할 경우 해당 기술이 적용된 모든 코드를 변경 해줘야 한다.

📌 POJO 프로그래밍이 필요한 이유

• 특정 환경 과 기술에 적용되지 않을때 재사용이 가능하고 확장이 가능하다.
• 환경에 종속적인 코드를 제거 함으로써 코드가 간결해지고 디버깅하기에 유리 하다
• 특정 기술과 환경에 종속적이지 않기 때문에 테스트가 단순 해진다.
• 객체지향적인 설계를 적용 할 수 있다.

📗 IOC (Inversion Of Control)

번역 하면 제어의 역전 이라고 칭할 수 있겠다.

비즈니스 로직을 작성하다보면 객체를 생성하는 경우가 잦은데 객체를 생성할때마다 매번 생명주기를 하나하나 직접 관리하기는 번거롭다고 생각한다.

따라서 매번 객체를 생성 하고 생명주기를 관리 하는 것을 스프링 컨테이너가 담당함에따라서 개발자의 부담을 덜어준다.

기존에 객체의 생성 및 생명유지를 위해 작성 된 코드들이 빠지면서 코드가 간결해지고 보다 관리함에 있어서 안정성이 좋아 질 것 이다.

📗 DI (Dependency Injection)

의존관계 주입 또는 의존성 주입 이라고 부르며 DI는 외부에서 객체 간의 관계(의존성)를 결정해 주는데 즉, 객체를 직접 생성하는 것이 아니라 외부에서 생성후 주입시켜 주는 방식이라고 할 수 있다.

class A{
    new b = new B();
    생략
}

class B{
    생략
}

예를들어 A 클래스가 B클래스를 이용할 때 A는 B에 의존한다 라고 표현 할 수 있을 것 이다. A는 B없이는 작동 할 수 없으며 의존대상인 B가 변경된다면 A에게 영향을 미치게 되며 강한 결합도를 가진다.

내부에서 B가 정의 되어 작동 하지않고 B클래스를 추상화 하여 정의하고 외부에서 정의된 B 객체가 주입된다면 B클래스가 추상화 범위 내에 변경 된다 하더라도 A 클래스가 변경되지 않도록 할 수 있게되며 결합도를 낮출 수 있다.

Spring에서 DI 방법에는 총 3가지가 있다.

• 생성자 주입
• 필드 주입
• Setter 주입

✔ 생성자 주입

현재 가장 권장되는 의존 관계 주입은 생성자 주입 방식이다. spring 공식 문서에서도 생성자 주입을 권장 하고 있으며 Lombok을 사용 한다면 @RequiredArgsConstructor를 통해서 의존성 주입이 가능하다.

생성자 주입은 생성자의 호출 시점에 1회 호출되는 것이 보장된다. 그렇기 때문에 주입받은 객체가 변하지 않거나, 반드시 객체의 주입이 필요한 경우에 강제하기 위해 사용할 수 있다.

@Service
pulbic class UserService {
    // final 붙일 수 있음
    private final UserRepository userRepository;

    // @Autowired (생략 가능)
    public UserService(UserRepository userRepository) {
        this.userRepository= userRepository;
        }
}

✔ 필드 주입

Intellij 에서 필드 주입방식을 사용 할 경우 Field injection is not recommended 경고 문구가 발생한다.

외부에서 수정이 불가능하므로 수정이 불가능한 필드 주입은 테스트 코드를 작성 함에 있어서는 사용가치가 떨어질 수 있다.

@Service
public class UserService {
    @Autowired
    private UserRepository userRepository;
}

✔ setter 주입

주입받는 객체가 변경될 가능성이 있는 경우에 주로 사용한다.

private class UserService {
    private UserRepository userRepository;
    @Autowired
    public void setUserRepository(UserRepository userRepository) {
        this.userRepository = userRepository;
    }
}

📗 AOP(Aspect Oriented Programming)

관점 지향 프로그래밍이라고 불린다. 어떤 로직을 기준으로 핵심적인 관점, 부가적인 관점으로 나누어 보고 그 관점을 기준으로 각각 모듈화 하겠다는 것. 공통된 로직이나 기능을 하나의 단위로 묶는 것을 모듈화라 칭한다. 만약 구현 코드의 기능이 조금씩 다르고 각 코드의 로깅, 성능을 측정하는 부분의 코드는 같다고 가정 했을때 로깅, 성능 측정 부분의 코드는 하나로 묶을 수 있을 것이다. 위와 같이 수정한다면 핵심 구현 코드의 수정은 필요하지 않으면서 공통 기능은 묶게 된다.

관점 지향 프로그래밍에서는 소스코드에서 반복적으로 사용하는 코드를 하나로 묶어서 모듈화하여 재사용성과 유지 보수성을 높일 수 있는 강점을 가지고 있다.

spring에서는 런타임 시점에 프록시 객체를 생성하여 공통 기능을 삽입 하는 방식으로 AOP를 구현 한다.

• Aspect - 공통적인 기능들을 모듈화 한것을 의미.
• Target - Aspect가 적용될 대상을 의미하며 메소드, 클래스 등이 이에 해당.
• Join point - Aspect가 적용될 수 있는 시점을 의미하며 메소드 실행 전, 후 등이 될 수 있다.
• Advice - Aspect의 기능을 정의한 것으로 메서드의 실행 전, 후, 예외 처리 발생 시 실행되는 코드를 의미.
• Point cut - Advice를 적용할 메소드의 범위를 지정한다.

프록시는 메서드 오버라이딩 개념으로 동작하기 때문에, 스프링 AOP는 메서드 실행 시점에만 AOP를 적용 할 수 있고 스프링 컨테이너가 관리할 수 있는 빈에만 적용 가능하다.

참고

https://velog.io/@sujin1018/%EC%8A%A4%ED%94%84%EB%A7%81-Spring-%EC%9D%98%EC%A1%B4%EC%84%B1-%EC%A3%BC%EC%9E%85-%EB%B0%A9%EB%B2%95-%EB%B0%8F-%EC%83%9D%EC%84%B1%EC%9E%90-%EC%A3%BC%EC%9E%85-%EB%B0%A9%EB%B2%95%EC%9D%98-%EC%9E%A5%EC%A0%90

https://engkimbs.tistory.com/entry/%EC%8A%A4%ED%94%84%EB%A7%81AOP

💻 제출

📌 입력

📌 출력

🤔 생각

생각해야 할 조건이 몇 가지 존재한다.

1. 연속되어 있는 여학생 7명을 선정 해야한다.
2. 선정할때 '임도연파'가 4명이상 포함 되어 있을 수 없다.

7명의 학생을 선정 할 때는

• 반복문 을 사용 한 자리 선정 ([백준 14502 - 연구소] 에서 사용) 아래 코드는 연구소 문제 기준으로 작성 된 코드

if (depth == 3) { bfs(); //벽이 완성 된 상태의 바이러스 안전지대 확인 return; }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0) { //벽을 세울 수 있는 빈 공간 이라면
                map[i][j] = 1; //현재 위치에 벽을 세우고
                dfs(depth + 1); //depth 1 추가 후 재귀
                map[i][j] = 0; //현재 위치를 다시 빈공간으로 복귀
                //이어서 반복분
            }
        }
    }

- 2차원 배열을 1차원으로 나열하여 계산
``` java

if (pY >= 4) { //임도연 파가 4명 이상이면 return
            return;
        }

        if (num == 7) { //이다솜 파가 4명 이상인 상태
            checkLinked(start - 1);
        } else {
            for (int i = start; i < (SIZE * SIZE); i++) {
                visited[i / SIZE][i % SIZE] = true;
                getPrincess(num + 1, map[i / SIZE][i % SIZE] == 'Y' ? pY + 1 : pY, i+1);
                visited[i / SIZE][i % SIZE] = false;
            }
        }

2차원 배열을 1차원 배열로 위 그림과 같이 표현 할 수 있고 가로 길이(M)로 나누게 된다면 2차원의 index를 구할 수 있다.

📝 코드

import java.io.*;
import java.util.*;

public class Main {
    static final int SIZE = 5;
    static char[][] map;
    static boolean[][] visited;
    static boolean[][] bfsVisited;
    static int[] dx = {0, 1, 0, -1}; //동 남 서 북
    static int[] dy = {1, 0, -1, 0}; //동 남 서 북
    static long result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        map = new char[SIZE][SIZE];
        visited = new boolean[SIZE][SIZE];

        for (int i = 0; i < SIZE; i++) {
            String line = br.readLine();
            map[i] = line.toCharArray();
        }

        getPrincess(0, 0,0);

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }

    static void getPrincess(int num, int pY, int start) {
        if (pY >= 4) { //임도연 파가 4명 이상이면 return
            return;
        }

        if (num == 7) { //이다솜 파가 4명 이상인 상태
            checkLinked(start - 1);
        } else {
            for (int i = start; i < (SIZE * SIZE); i++) {
                visited[i / SIZE][i % SIZE] = true;
                getPrincess(num + 1, map[i / SIZE][i % SIZE] == 'Y' ? pY + 1 : pY, i+1);
                visited[i / SIZE][i % SIZE] = false;
            }
        }
    }

    static void checkLinked(int start) {
        bfsVisited = new boolean[SIZE][SIZE];

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{start / SIZE, start % SIZE});

        bfsVisited[start / SIZE][start % SIZE] = true;
        int cnt = 1;

        while (!q.isEmpty()) {
            int size = q.size();

            for (int s = 0; s < size; s++) {
                int[] poll = q.poll();
                int x = poll[0];
                int y = poll[1];

                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];

                    if (0 <= nx && nx < SIZE && 0 <= ny && ny < SIZE) {
                        if (visited[nx][ny] == true && bfsVisited[nx][ny] == false){
                            q.offer(new int[] {nx,ny});
                            cnt++;
                            bfsVisited[nx][ny] = true;
                        }
                    }
                }

            }
        }

        if (cnt == 7){
            result++;
        }
    }
}

7명의 여학생을 배정하고 연속되어 있는지를 확인 할 때는 visited 배열을 사용했는데 해당 배열만으로 진행한다면 큐에 데이터를 넣고 꺼내는 과정에서 탐색했던 부분을 반복할 우려가 있다. 따라서 진행했던 부분을 중복하여 탐색하지 않기 위해서 추가 배열 bfsVisited를 선언해서 진행해 주었다.

연속 여부를 체크하는 BFS 탐색이 끝난다면 cnt를 계산 해주는데 cnt를 연속되어 있는 학생의 숫자이다. cnt == 7이면 칠공주가 완성된 것이다.

📗 정리

DFS , BFS를 사용해서 탐색하는 코드는 구현하는 것에 나름 익숙해져 있는데 전체 배열에서 무작위로 자리를 배정하는 경우는 익숙하지 않았었다.

과거에 비슷하게 배정하는 문제를 풀었던 기억이 얼핏 들어서 연구소 문제를 복기 했다.

다양한 방법으로 접근을 시도 하면서 두가지 방법(반복문 , 1차원 배열 변환) 모두 동일한 결과를 반환 한다는 것을 알아냈고 좀 더 직관적이라고 생각한 1차원 배열로 이번 문제를 풀어 보았다.

연구소 문제를 풀었을 당시에는 작동 원리에 대해서 긴가민가 했었는데 운 좋게 이번 문제를 접하면서 한번 더 공부 하게 될 수 있었다.

백 트래킹을 학습하지 않은 상태라 제대로 적용하지 못했는데 제대로 적용 할 수 있다면 코드가 더 깔끔 해질 것 같다.

💻 제출

📌 입력

📌 출력

🤔 생각

트리를 쭉 늘어뜨리기 위해서 어떤 방법이 있을까 생각 해봤는데 가장 큰 지름을 갖기 위해서는 트리의 리프 노드를 두개 잡아야 한다.

트리의 리프노드를 확인 하기 위해서는 간선이 1개 연결 되어있는 것을 찾아야 한다.

모든 리프 노드를 깊이 우선 탐색 하면서 Depth를 계산 해보자.

📝 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static ArrayList<Node>[] tree;
    static boolean[] visited;
    static long maxD = 0;

    static class Node{
        int n;
        long distance;

        public Node(int n, long distance) {
            this.n = n;
            this.distance = distance;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        visited = new boolean[N+1];
        tree = new ArrayList[N+1];

        for (int i=1; i<=N; i++){
            tree[i] = new ArrayList<>();
        }

        for (int i = 0; i < N-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());

            tree[s].add(new Node(e,distance)); //양방향 연결
            tree[e].add(new Node(s,distance));
        }

        for (int i = 1; i <= N; i++) {
            if (tree[i].size() == 1){
                //leaf 노드라면?
                Arrays.fill(visited,false);
                dfs(i , 0);
            }
        }


        bw.write(maxD + "\n");
        bw.flush();
        bw.close();
    }

    static void dfs(int start , long depth) {
        visited[start] = true;

        if (tree[start].size() == 1 && depth > 0){
            maxD = Math.max(maxD , depth);
            return;
        }

        for (Node next : tree[start]){
            //연결된 간선 탐색
            int nextN = next.n; //다음 노드 번호
            long nextD = next.distance; //다음 노드 까지의 간선 거리

            if (visited[nextN] == false){
                dfs(nextN, depth + nextD);
            }
        }
    }

}

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

💻 제출

📌 입력

📌 출력

📌 제한

🤔 생각

해당 문제를 읽었을때 단계를 나누어서 풀어야 할 것 같다고 생각이 들었다.

1. L값에 따라 영역을 분류 하기
2. 분류한 영역을 rotate 하면서 값 변동 하기
3. 인접한 얼음 영역이 2개 이하면 해당 영역 값 줄여주기
4. 주어진 Q값에 따라 1 ~ 3을 반복 하기

📝 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, Q;
    static int[] L;
    static int[][] map;
    static int[] dx = {0, 1, 0, -1}; //동 남 서 북 x좌표
    static int[] dy = {1, 0, -1, 0}; //동 남 서 북 y좌표
    static boolean[][] visited;
    static long maxIce = 0;
    static long maxLand = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        N = Integer.parseInt(st.nextToken()); //N
        Q = Integer.parseInt(st.nextToken()); //시전 횟수
        N = (int)Math.pow(2,N);

        map = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer stD = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(stD.nextToken());
            }
        }

        L = new int[Q];
        StringTokenizer stL = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < Q; i++) {
            L[i] = Integer.parseInt(stL.nextToken());
        }

        for (int i = 0; i < Q; i++) {
            map = divide(L[i]);
            map = melt();
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                maxIce += map[i][j];
                if (map[i][j] != 0 && visited[i][j] == false){ //얼음 영역 이라면
                    bfs(i,j);
                }
            }
        }

        bw.write(maxIce + "\n");
        bw.write(maxLand + "\n");
        bw.flush();
        bw.close();
    }

    static int[][] divide(int l) { //구역을 나누기
        int[][] replaceArea = new int[N][N];
        int powL = (int) Math.pow(2, l); // 2^l 으로 제곱 연산

        for (int i = 0; i < N; i += powL) {
            for (int j = 0; j < N; j += powL) {
                rotateIce(i, j, powL, replaceArea);
            }
        }
        return replaceArea;
    }

    static void rotateIce(int x, int y, int powL, int[][] replaceArea) {
        for (int i = 0; i < powL; i++) {
            for (int j = 0; j < powL; j++) {
                replaceArea[j + x][powL - 1 - i + y] = map[x + i][y + j];
            }
        }
    }

    static int[][] melt() {
        int[][] replaceArea = new int[N][N];

        for (int i = 0; i < N; i++) {
            replaceArea[i] = Arrays.copyOf(map[i], N);
        }

        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                int cnt = 0;

                if (map[x][y] == 0) {
                    continue; //이미 얼음이 다녹은 칸
                }

                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];

                    if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                        if (map[nx][ny] > 0) {
                            cnt++; //얼음이 주변에 있음
                        }
                    }
                }

                if (cnt < 3) {
                    replaceArea[x][y]--; //임시 배열 얼음 값 감소
                    //주변 3면 이상이 얼음 영역 아님
                }
            }
        }
        return replaceArea;

    }

    static void bfs(int x,int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x,y});

        visited[x][y] = true;
        long land = 1;

        while (!q.isEmpty()){
            int[] now = q.poll();

            for (int i=0; i<4; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];

                if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                    if (visited[nx][ny] == false && map[nx][ny] > 0){
                        land++;
                        visited[nx][ny] = true;
                        q.offer(new int[] {nx,ny});
                    }
                }
            }
        }
        maxLand = Math.max(land,maxLand);
    }

}

📑 영역 분리

        L = new int[Q];
        StringTokenizer stL = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < Q; i++) {
            L[i] = Integer.parseInt(stL.nextToken());
        }

        for (int i = 0; i < Q; i++) {
            map = divide(L[i]);
            map = melt();
        }

static int[][] divide(int l) { //구역을 나누기
        int[][] replaceArea = new int[N][N];
        int powL = (int) Math.pow(2, l); // 2^l 으로 제곱 연산

        for (int i = 0; i < N; i += powL) {
            for (int j = 0; j < N; j += powL) {
                rotateIce(i, j, powL, replaceArea);
            }
        }
        return replaceArea;
    }

L값이 오름차순으로 진행 되는 것이 아니라 주어진 입력값에 따라 다르게 적용 되야 하므로 배열에 저장 후 반복문을 divide 함수를 호출 한다.

주어진 L값을 제곱 연산 하고 반복문 i,j를 제곱 연산 값만큼 증가 시켜 주면 영역을 분리 할 수 있다. 분리한 영역의 첫번째 좌표 값을 기준으로 rotateIce 함수가 호출 된다.

📑 회전

static void rotateIce(int x, int y, int powL, int[][] replaceArea) {
        for (int i = 0; i < powL; i++) {
            for (int j = 0; j < powL; j++) {
                replaceArea[j + x][powL - 1 - i + y] = map[x + i][y + j];
            }
        }
    }

한번에 회전을 해야 하기 때문에 임시 배열인 replace를 생성 해줬으며 replace의 x 와 map 의 y값은 동일한 규칙을 확인 할 수 있다. replace 의 y 값은 주어진 L의 제곱 값 - i - 1 연산으로 구할 수 있다.

이후 영역의 첫번째 값을 각 좌표에 전부 더해주면

replaceArea[j + x][powL - 1 - i + y] = map[x + i][y + j];

를 얻을 수 있다.

📑 얼음 녹이기

static int[][] melt() {
        int[][] replaceArea = new int[N][N];

        for (int i = 0; i < N; i++) {
            replaceArea[i] = Arrays.copyOf(map[i], N);
        }

        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                int cnt = 0;

                if (map[x][y] == 0) {
                    continue; //이미 얼음이 다녹은 칸
                }

                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];

                    if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                        if (map[nx][ny] > 0) {
                            cnt++; //얼음이 주변에 있음
                        }
                    }
                }

                if (cnt < 3) {
                    replaceArea[x][y]--; //임시 배열 얼음 값 감소
                    //주변 3면 이상이 얼음 영역 아님
                }
            }
        }
        return replaceArea;

    }

모든 영역을 상 하 좌 우 이동하면서 인접 영역을 탐색한다. 주변에 얼음 수가 2개 이하라면 현재 영역의 값을 줄여주며 진행 하면 된다.

📑 가장 큰 덩어리 값 계산

static void bfs(int x,int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x,y});

        visited[x][y] = true;
        long land = 1;

        while (!q.isEmpty()){
            int[] now = q.poll();

            for (int i=0; i<4; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];

                if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                    if (visited[nx][ny] == false && map[nx][ny] > 0){
                        land++;
                        visited[nx][ny] = true;
                        q.offer(new int[] {nx,ny});
                    }
                }
            }
        }
        maxLand = Math.max(land,maxLand);
    }

bfs로 탐색 하여 연결된 영역 얼음 합산의 가장 큰 값을 구한다.

📗 정리

현재까지 풀었던 문제 중에서 가장 어렵다고 느껴졌다.

이상하게 rotate 함수를 구현 할 때 공식을 찾지 못해서 많은 시간을 허비 했다.

전부 구현 하고 다시 돌아봤을 때는 어려운 문제가 아니라고 생각이 드는데 풀이 당시에는 왜 그렇게 생각이 안 났는지 모르겠다.

수학 문제를 푼 지 한참 지나서 머리가 굳어버린 것 일지도.

문제에 표시되는 티어가 높아 질 수록 풀이 단계가 점점 많아지지만 분리 해서 구현 해나가다 보면 난해 하지는 않은 것 같다.

학교 생활을 하면서 프로젝트에 대부분의 시간을 쏟았기 때문에 코딩테스트는 손을 대지 않았었다.

코딩테스트라는 것에 대해 부정적인 생각도 가지고 있었기 때문에 더 멀리 했던 것 같다.

프로젝트만 으로 충분히 경쟁력을 가질 수 있을 것 이라고 생각 했는데 코딩테스트를 손도 대지 못한다면 취업시장의 문턱도 제대로 밟지 못하는 것을 느껴버렸다.

코딩테스트를 통과 하지 못한다면 프로젝트를 아무리 열심히 했어도 어필 할 수가 없다.

준비를 시작한지 한달의 시간이 흘렀는데 한달동안 여러가지 유형을 건드리는 것 보다는 하나의 유형에 감을 익히고 넘어가는 것이 좋다고 판단 했다.

한달 동안 합 배열, 투 포인터, window slider, DFS, BFS, graph 만 문제를 풀었던 것 같다.

나열한 유형의 실버 문제들은 대부분 쉽게 푸는 것 같고 골드 하위 들은 아직 버벅거리는 것 같다.

골드 중위 ~ 상위 부터는 알고리즘이 섞여서 나오는 느낌이라 이후 부터는 다른 유형을 공부 해보려 한다.

개인적인 생각으로 프로젝트가 개발 경력으로 인정된다면 코테와 절반 정도의 중요성을 나눠 갖는 것 같고 경력이 없는 쌩 신입으로 취직하려 한다면 코딩테스트 >>>>> 프로젝트 인 것 같다는 생각이 자주 든다. 😂

💻 제출

📌 입력

📌 출력

🤔 생각

문제에 생각보다 고려 할 점이 많다.

상어는 본인보다 작은 물고기 만 먹을 수 있고 자신의 level보다 큰 물고기 영역에는 접근 할 수 없다. 이동 할 때는 빈 공간 과 자신과 level이 동일 하거나 낮은 영역으로 이동 해야 한다. 또한 동일한 거리에 물고기가 존재 한다면 위쪽 -> 왼쪽 -> 오른쪽 -> 아래쪽 으로 우선순위를 가진다.

위 우선순위가 문제를 푸는 가장 골칫거리 이자 해결할 수 있는 열쇠 라고 생각 했다.

물고기의 우선순위가 존재 하기 때문에 좌표 값을 확인 하면서 진행 해야하는데 매번 값을 꺼내서 직접 확인 하는 것 보다 우선순위 큐를 사용 하여 자동으로 정렬이 되도록 했다.

📝 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[][] map;
    static long fish = 0;
    static Shark start;
    static int[] dx = {-1, 0, 0, 1}; //북 서 동 남
    static int[] dy = {0, -1, 1, 0}; //북 서 동 남

    static class Shark {
        int x;
        int y;
        int level;
        int levelCnt;
        long d;

        public Shark(int x, int y, int level, int levelCnt, long d) {
            this.x = x;
            this.y = y;
            this.level = level;
            this.levelCnt = levelCnt;
            this.d = d;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 9) {
                    start = new Shark(i, j, 2,2,0);
                } else if (map[i][j] != 9 && map[i][j] != 0) {
                    fish++;
                }
            }
        }

        while (fish != 0) { //모든 물고기가 없어질 때 까지

            Shark S = bfs(start);

            if(S == null){
                break;
            }
            else{
                start = S;
            }
        }

        bw.write(start.d + "\n");
        bw.flush();
        bw.close();
    }

    static Shark bfs(Shark start) {
        PriorityQueue<Shark> q = new PriorityQueue<>((a, b) ->
                a.d != b.d ?
                        Long.compare(a.d,b.d) :  // distance 가 다르다면 오름차순 반환 (true)
                        (a.x != b.x ? //distance 가 같다면 x좌표 비교
                                Integer.compare(a.x,b.x) : //x좌표 다르다면 x좌표 오름차순 반환
                                Integer.compare(a.y,b.y) //x 좌표가 같다면 y좌표 오름차순 반환
                        )
        );

        q.offer(start);
        map[start.x][start.y] = 0; //처음 시작 위치는 빈공간으로 변경

        boolean[][] visited = new boolean[N][N];
        visited[start.x][start.y] = true;

        while (!q.isEmpty()) {
            Shark nowS = q.poll();

            if (map[nowS.x][nowS.y] != 0  && map[nowS.x][nowS.y] < nowS.level){
                //상어보다 level 이 낮은 물고기 공간

                fish--; //전체 물고기 감소
                map[nowS.x][nowS.y] = 0; //빈 공간으로 취급

                if (nowS.levelCnt - 1 == 0){ //업그레이드에 필요한 물고기 수 1 감소
                    //업그레이드에 필요한 물고기 개수를 다 채웠다면

                    //현재 level 증가
                    //level 증가한 만큼 cnt 도 변화
                    return new Shark(nowS.x,nowS.y, nowS.level + 1, nowS.level + 1 , nowS.d);
                }
                else{
                    return new Shark(nowS.x,nowS.y, nowS.level, nowS.levelCnt - 1 , nowS.d);
                    //물고기 먹은 개수만 줄여준다
                }
            }

            //물고기 영역이 아니라면
            for (int i=0; i<4; i++){
                int nx = nowS.x + dx[i];
                int ny = nowS.y + dy[i];

                if (0<=nx && nx<N && 0<=ny && ny<N){
                    if (visited[nx][ny] == false && map[nx][ny] <= nowS.level){
                        //방문하지 않았던 영역이어야 하고
                        //상어의 level 보다 낮거나 같은 영역으로 이동 가능

                        q.offer(new Shark(nx,ny, nowS.level, nowS.levelCnt, nowS.d+1));
                        visited[nx][ny] = true;
                    }
                }
            }

        }

        return null;
    }

}

📗 정리

PriorityQueue<Shark> q = new PriorityQueue<>((a, b) ->
                a.d != b.d ?
                        Long.compare(a.d,b.d) :  // distance 가 다르다면 오름차순 반환 (true)
                        (a.x != b.x ? //distance 가 같다면 x좌표 비교
                                Integer.compare(a.x,b.x) : //x좌표 다르다면 x좌표 오름차순 반환
                                Integer.compare(a.y,b.y) //x 좌표가 같다면 y좌표 오름차순 반환
                        )
        );

이번 문제의 가장 핵심 코드 라고 생각한다.

우선순위를 정할 때 distance , x좌표 , y좌표를 모두 고려 해야 한다.

꼬리에 꼬리를 무는 삼항 연산자를 사용 하여 진행 했으며 해당 코드로 인해 귀찮은 확인 작업을 직접 해주지 않아도 물고기의 우선순위는 자동으로 정렬 된다.

일반 queue를 사용하면 물고기의 우선순위를 직접 체크 해줘야 하기 때문에 코드가 어렵고 복잡해질 것 같았다.

우선순위 큐에 많은 조건을 걸어보는 것이 익숙치 않아서 정상적으로 수행이 될까 걱정 했지만 결과가 좋아서 다행이다.

다른 문제를 해결 할때도 우선순위 큐를 종종 넣어서 시도 할 생각이다.

💻 제출

문제에 나와있는 테스트 예제만 보고 DFS로 풀이 하려고 시도 했다. 하지만 허를 찌르는 반례가 하나 있었고 DFS로는 풀이하기 어지러워서 BFS로 급하게 노선을 틀었다.

비슷한 문제가 하나 더 있었는데 그때 코드와 크게 다르지는 않다.

📌 입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

📌 출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

🤔 생각

백준 2636 - 치즈

해당 문제는 이전 치즈 문제와 다르게 공기 영역이 두번이상 닿아야 사라진다. BFS로 탐색하면서 공기영역이 몇번 닿는지를 카운트 한다. max = 2 2번 닿으면 해당 치즈 영역을 빈 공간으로 바꿔주면 될 듯 하다.

모든 치즈가 사라질 때 까지 BFS탐색을 반복한다.

시간과 메모리 제한이 빡빡해서 최소한의 과정으로 풀어야 한다고 생각 했다. 본인은 시간제한 1초 , 메모리 제한 128MB 면 그냥 빡빡하다고 생각한다.

📝 첫번째 코드(실패, DFS 사용)

import java.io.*;
import java.util.*;


public class Main {
    static int N, M;
    static int[][] map;
    static int cheeseCnt = 0;
    static int time = 0;
    static int[] dx = {0, 1, 0, -1}; //동 남 서 북
    static int[] dy = {1, 0, -1, 0}; //동 남 서 북

    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            StringTokenizer stD = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                int data = Integer.parseInt(stD.nextToken());

                if (data == 1) { //치즈 개수 계산
                    cheeseCnt++;
                }

                map[i][j] = data;
            }
        }

        while (cheeseCnt != 0) {
            //맵에 치즈가 존재 하지 않을 때 까지 반복
            for (int i=0; i<N; i++){
                for (int j=0; j<M; j++){
                    if (map[i][j] == 1){
                        for (int v=0; v<N; v++){
                            Arrays.fill(visited[v],false);
                        }
                        time++;
                        dfs(i,j);
                    }
                }
            }
        }


        bw.write(time + "\n");
        bw.flush();
        bw.close();
        br.close();
    }


    static void dfs(int x,int y) {
        visited[x][y] = true;
        int cnt = 0;

        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0<=nx && nx<N && 0<=ny && ny<M){
                //영역 안에 있어야 함
                if (visited[nx][ny] == false){ //다음 영역이 방문하지 않은 상태 라면
                    if (map[nx][ny] == 0){ //공기가 닿는 부분
                        cnt++;
                    }
                    else{
                        dfs(nx,ny);
                    }
                }
            }
        }

        if (cnt>=2){
            map[x][y] = 0; //사라지는 치즈
            cheeseCnt--;
        }
    }

}

치즈 영역으로 부터 처음 시작해서 동 남 서 북 시계 방향으로 깊이 우선 탐색을 시작한다. 다음 영역이 공기 영역이라면 cnt를 해주기 때문에

if (visited[nx][ny] == false){ //다음 영역이 방문하지 않은 상태 라면
                    if (map[nx][ny] == 0){ //공기가 닿는 부분
                        cnt++;
                    }
                    else{
                        dfs(nx,ny);
                    }
                }

재귀가 끝나고 cnt가 2이상 이라면 빈 영역으로 변환 한다.

if (cnt>=2){
            map[x][y] = 0; //사라지는 치즈
            cheeseCnt--;
        }

하지만 위와 같은 코드로는 풀 수 없는 반례가 있다.

7 7
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 1 0 1 0 0
0 1 0 1 0 1 0
0 0 1 0 1 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0

와 같은 반례가 주어질때 모든 1이 인접해 있지 않기 때문에 각 1은 다른 시간 대로 판단 한다. <= 허점

또한 내부 공간에 대한 고려 역시 따로 필요 하므로 정상적인 결과를 받아 낼 수 없다.

📝 두번째 코드(정상 제출, BFS 사용)

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[][] map;
    static int cheeseCnt = 0;
    static int time = 0;
    static int[] dx = {0, 1, 0, -1}; //동 남 서 북
    static int[] dy = {1, 0, -1, 0}; //동 남 서 북

    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            StringTokenizer stD = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                int data = Integer.parseInt(stD.nextToken());

                if (data == 1) { //치즈 개수 계산
                    cheeseCnt++;
                }

                map[i][j] = data;
            }
        }

        while (cheeseCnt != 0) {
            //맵에 치즈가 존재 하지 않을 때 까지 반복
            bfs();
            time++;
        }


        bw.write(time + "\n");
        bw.flush();
        bw.close();
        br.close();
    }


    static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});

        boolean visited[][] = new boolean[N][M];
        visited[0][0] = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int nowX = now[0];
            int nowY = now[1];

            for (int i = 0; i < 4; i++) {
                int nx = nowX + dx[i];
                int ny = nowY + dy[i];

                if (0 <= nx && nx < N && 0 <= ny && ny < M){
                    if (map[nx][ny] == 1 && visited[nx][ny] == true){
                        //현재 방문이 두번째 방문 이라면 , 공기에 두번 닿는 상태
                        map[nx][ny] = 0;
                        cheeseCnt--;
                    }

                    if (visited[nx][ny] == false){
                        if (map[nx][ny] == 1){
                            visited[nx][ny] = true; //공기에 1번 닿은 상태 
                        }
                        else if (map[nx][ny] == 0){
                            visited[nx][ny] = true;
                            q.offer(new int[] {nx,ny});
                        }
                    }
                }
            }
        }
    }

}

내부 공기 영역에 대한 고려가 필요없는 BFS를 통해 가장자리 부터 접근 을 시도 했다.

공기 영역은 큐에 넣어주면서 탐색을 이어가고 치즈 영역은 접근을 두가지로 분리 하여 시도 했다.

한번이라도 방문을 한다면 치즈, 공기 영역에 상관 없이 visited[index] = true; 로 변환 되기 때문에 flag의 역할이 가능하다.

if (map[nx][ny] == 1 && visited[nx][ny] == true){
   //현재 방문이 두번째 방문 이라면 , 공기에 두번 닿는 상태
    map[nx][ny] = 0;
    cheeseCnt--;
}

이후 두번째 접근 시도가 발생한다면 해당 공간을 빈 공간으로 바꿔준다.

📗 정리

이번 문제보다 난이도가 낮은 치즈 문제를 한번 풀어 봤던 경험이 있기 때문에 금방 풀 수 있었던 것 같다.

이번 문제 역시 난이도가 높지는 않지만 한번 경험했던 유형은 체감 난이도가 급격하게 떨어지는 것 같으며 많은 문제를 접하는게 문제 풀이 속도에 큰 영향을 줄 것이라 생각 한다.

문제 자체가 재밌다고 생각이 들어서 빨리 해결 했다고도 생각 한다.

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

💻 제출

📌 입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

📌 출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

🤔 생각

해당 문제를 봤을 때 4자리 수에 해당하는 모든 수를 배열에 저장 해놓고 password 변경 시에 배열에 속하는 숫자인지 확인 하는 식으로 풀이 하기로 했다.

ArrayList<Integer> primeNum 를 선언 하고 isPrime 함수를 통해 1000 ~ 9999 까지 소수를 판별 한다.

static boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) { //제곱근 까지만 순회해도 소수 판별 가능
            if (num % i == 0) {
                return false;
            }
        }

        return true; //소수 임
    }

전체 숫자를 순회 해도 상관 없지만 주어진 숫자의 제곱근 까지만 순회 해도 소수는 판별이 가능 하다.

배열 안에 모든 4자리 숫자가 저장 되었다면 각 자리 비밀번호를 변경 하면서 BFS탐색을 진행 한다.

📝 코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    static int T, S, E;
    static ArrayList<Integer> primeNum = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        T = Integer.parseInt(br.readLine());

        for (int i = 1000; i <= 9999; i++) { //4자리 수 시작
            if (isPrime(i) == true) {
                primeNum.add(i);
            }
        }

        for (int t = 0; t < T; t++) {
            StringTokenizer stL = new StringTokenizer(br.readLine(), " ");

            S = Integer.parseInt(stL.nextToken()); // 시작 번호
            E = Integer.parseInt(stL.nextToken()); // 타겟 번호

            if (S == E){
                bw.write("0\n");
                continue;
            }
            int depth = bfs(S);

            bw.write(depth != -1 ? (depth + "\n") : "Impossible\n");
        }

        bw.flush();
        bw.close();
    }

    static boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) { //제곱근 까지만 순회해도 소수 판별 가능
            if (num % i == 0) {
                return false;
            }
        }

        return true; //소수 임
    }

    static int bfs(int start) {
        //시작 숫자가 소수 배열 몇번째 index 를 가지는지 확인
        int findIdx = primeNum.indexOf(start);
        int depth = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(findIdx);

        boolean[] visited = new boolean[primeNum.size()];
        visited[findIdx] = true;

        while (!q.isEmpty()) {
            int size = q.size();

            for (int s = 0; s < size; s++) {
                Integer cIdx = q.poll(); //현재 비밀번호 index
                int nowP = primeNum.get(cIdx); //현재 비밀번호 값

                if (nowP == E) { //찾았다면
                    return depth;
                }

                //천의 자리수 변경
                for (int i = 1; i < 10; i++) { //1 ~ 9
                    int nextP = (i * 1000) + (nowP % 1000);

                    if (primeNum.contains(nextP) && nextP != nowP) {
                        //바뀐 숫자가 소수 여야함
                        //바뀌기 전 숫자와 달라야 함
                        int nextIdx = primeNum.indexOf(nextP); //바뀐 숫자 Index
                        if (visited[nextIdx] == false) {
                            q.offer(nextIdx);
                            visited[nextIdx] = true;
                        }
                    }

                }
                //백의 자리 수 변경
                for (int i = 0; i < 10; i++) { //0 ~ 9
                    int nextP = ((nowP / 1000) * 1000) + (i * 100) + (nowP % 100);

                    if (primeNum.contains(nextP) && nextP != nowP) {
                        //바뀐 숫자가 소수 여야함
                        //바뀌기 전 숫자와 달라야 함
                        int nextIdx = primeNum.indexOf(nextP); //바뀐 숫자 Index
                        if (visited[nextIdx] == false) {
                            q.offer(nextIdx);
                            visited[nextIdx] = true;
                        }
                    }

                }

                //십의 자리 수 변경
                for (int i = 0; i < 10; i++) { //0 ~ 9
                    int nextP = ((nowP / 100) * 100) + (i * 10) + (nowP % 10);

                    if (primeNum.contains(nextP) && nextP != nowP) {
                        //바뀐 숫자가 소수 여야함
                        //바뀌기 전 숫자와 달라야 함
                        int nextIdx = primeNum.indexOf(nextP); //바뀐 숫자 Index
                        if (visited[nextIdx] == false) {
                            q.offer(nextIdx);
                            visited[nextIdx] = true;
                        }
                    }

                }

                //일의 자리 수 변경
                for (int i = 0; i < 10; i++) { //0 ~ 9
                    int nextP = ((nowP / 10) * 10) + i;

                    if (primeNum.contains(nextP) && nextP != nowP) {
                        //바뀐 숫자가 소수 여야함
                        //바뀌기 전 숫자와 달라야 함
                        int nextIdx = primeNum.indexOf(nextP); //바뀐 숫자 Index
                        if (visited[nextIdx] == false) {
                            q.offer(nextIdx);
                            visited[nextIdx] = true;
                        }
                    }

                }
            }

            depth++;
        }

        return -1;
    }

}

📗 정리

원래는 password가 주어진다면 소수 배열에서 해당 숫자의 index를 찾아낸 후 index를 +1 , -1 해주면서 BFS 탐색을 하려 했다.

하지만 위와 같이 탐색을 진행 하는 경우 1의 자리부터 순차적으로 값을 변경 하면서 depth를 증가 시키기 때문에 예제에서 원하는 return 값을 절대로 받아 낼 수 없다.

단순히 가능한지 여부만 판단한다면 가능 할 수도 있겠다.

따라서 각 자리 숫자 변경을 통해서 변경 된 수를 큐에 넣어주면서 경우의 수를 탐색 했다.

기존 접근 했던 숫자는 visited배열을 통해 중복 접근 하지 못하게 설정 해 주었다.

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