더 이상 물러설 곳이 없다

객체가 RDB에 매핑될 때 반드시 PK로 사용할 멤버변수를 지정해줘야 한다.

이때 @Id 어노테이션을 사용하는데, 이것만 사용할 경우 다른 컬럼들과 똑같이 PK값도 일일히 직접 할당해주게 된다.

보통 PK에 대해서는 이런 식으로 하지 않고 값이 알아서 자동적으로 할당되도록 하는 것이 좋다.

이를 위해 @Genera5tedValue 어노테이션을 추가로 사용하는데 여기에 적용되는 여러 가지 옵션이 있다.

그 중 가장 대표적인 방식은 IDENTITY, SEQUENCE 방식이다.

1. IDENTITY

@Entity 
public class Member { 
    @Id 
    @GeneratedValue(strategy = GenerationType.IDENTITY) 
    private Long id; 
}

PK의 생성을 데이터베이스가 대신 할당하도록 한다. 주로 MySQL에서 사용되는 방식이다.

(오라클은 IDENTITY 지원하지 않음)

IDENTITY 전략을 사용할 때 영속성 컨텍스트는 평소와는 조금 다르게 동작한다.

em.persist()로 영속성 컨텍스트에 객체를 저장하게 되면 해당 객체는 영속성 컨텍스트에 있는 1차 캐시 안에서 Key-Value 쌍으로 존재하게 된다.

이때 Key = PK, Value = Object의 형태로 존재하게 되는데.. IDENTITY 방식은 엔티티가 실질적으로 DB에 저장되는 순간 DB에서 자동으로 PK값을 할당해주는 방식이다.

하지만 트랜잭션이 커밋되기 전까지 해당 객체에 대한 쿼리는 DB에 적용되지 않는다. 

즉, 커밋이 이뤄지기 전까지는 PK를 가질 수 없다는 것. 그런데 영속성 컨텍스트 안에서는 PK-Object의 키밸류 페어로 존재해야 한다.

이를 해결하기 위해서 IDENTITY 전략을 사용할 때는 예외적으로 em.persist()를 호출했을 때 즉각적으로 DB에 실제 쿼리를 날려버린다.

2. SEQUENCE

@Entity 
@SequenceGenerator( 
        name = “MEMBER_SEQ_GENERATOR", 
        sequenceName = “MEMBER_SEQ", // 매핑할 데이터베이스 시퀀스 이름
        initialValue = 1, allocationSize = 1) 
public class Member { 
    @Id 
    @GeneratedValue(strategy = GenerationType.SEQUENCE, 
            generator = "MEMBER_SEQ_GENERATOR") 
    private Long id; 
}

SEQUENCE 전략은 DB의 시퀀스 오브젝트를 사용하여 PK값을 자동할당한다. 주로 오라클 디비에서 사용되는 방식이다.

(MySQL은 SEQUENCE 지원하지 않음)

이를 위해 @SequenceGenerator를 통해 사용할 시퀀스 오브젝트를 직접 생성해줘야 한다.

em.persist()를 수행하면 DB의 시퀀스 오브젝트에게서 1차캐시에 Key값으로 저장될 PK값을 할당받아 객체와 함께 영속성 컨텍스트 안에 저장한다.

(이떄 IDENTITY 전략 처럼 DB에 쿼리가 날아가는 것은 아니다)

하지만 PK 하나가 필요할 때마다 매번 디비쪽과 네트워크 통신을 하기 때문에 성능에 대한 문제가 있을 수 있다. 이를 방지하기 위해 @SequenceGenerator의 allocationSize 속성이 존재한다.

allocationSize는 한 번의 시퀀스 접근을 통해 사용할 수 있는 PK값의 개수를 의미한다.

allocationSize의 디폴트 값은 50인데, 이 경우 한 번의 DB 접근만으로 50개의 PK값을 얻어와 메모리에 저장한 뒤 영속성 컨텍스트에 객체를 저장할 때마다 메모리에서 PK를 하나씩 가져와 할당하는 것이다.

이렇게 하면 네트워크 접근 횟수를 비약적으로 줄일 수 있게 된다.

시퀀스 동작에 대한 좀 더 자세한 설명은 아래 질문글 링크를 참고

https://www.inflearn.com/questions/116520

www.acmicpc.net/problem/14442

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제 입력 1

6 4 1

0100

1110

1000

0000

0111

0000

예제 출력 1

15

예제 입력 2

6 4 2

0100

1110

1000

0000

0111

0000

예제 출력 2

9

예제 입력 3

4 4 3

0111

1111

1111

1110

예제 출력 3

-1

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair {
    int r, c, d, cnt;
    Pair(int r, int c, int d, int cnt) {
        this.r = r;
        this.c = c;
        this.d = d;
        this.cnt = cnt;
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[][] map = null;
    static boolean[][][] check = null;
    static int N, M, K, ans = -1;
    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1, 1};

    public static void bfs() {
        Queue<Pair> que = new ArrayDeque<>();
        que.add(new Pair(0, 0, 0, 1));
        check[0][0][0] = true;

        while(!que.isEmpty()) {
            Pair p = que.poll();
            int r = p.r, c = p.c, d = p.d, cnt = p.cnt;
            if(r == N - 1 && c == M - 1) {
                ans = cnt;
                return;
            }

            for(int i = 0; i < 4; i++) {
                int nr = r + rArr[i];
                int nc = c + cArr[i];
                if(-1 < nr && nr < N && -1 < nc && nc < M) {
                    if(map[nr][nc] == 1) {  // 다음 좌표가 벽
                        if(d < K && !check[nr][nc][d+1]) {  // 아직 벽을 더 뚫을 수 있으면 계속 진행
                            que.add(new Pair(nr, nc, d + 1, cnt + 1));
                            check[nr][nc][d+1] = true;
                        }
                    }else {  // 다음 좌표 뚫려있음
                        if(!check[nr][nc][d]) {
                            que.add(new Pair(nr, nc, d, cnt + 1));
                            check[nr][nc][d] = true;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        check = new boolean[N][M][K+1];
        for(int i = 0; i < N; i++) {
            String str = br.readLine();
            for(int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }

        bfs();
        System.out.println(ans);
    }
}

codeung.tistory.com/24 에서 K 제한만 추가된 문제.

조건문을 조금 수정하여 바로 해결했다.

www.acmicpc.net/problem/1726

문제

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

• 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
• 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때,  이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.

로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다. 이때 M과 N은 둘 다 100이하의 자연수이다. 이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다. 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

출력

첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.

예제 입력 1

5 6

0 0 0 0 0 0

0 1 1 0 1 0

0 1 0 0 0 0

0 0 1 1 1 0

1 0 0 0 0 0

4 2 3

2 4 1

예제 출력 1

9

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair {
    int r, c, dir, cnt;
    Pair(int r, int c, int dir, int cnt) {
        this.r = r;
        this.c = c;
        this.dir = dir;
        this.cnt = cnt;
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[][] map = null;
    static boolean[][][] check = null;

    static Pair begin = null;
    static Pair end = null;
    static int N, M, ans;

    // [0, 1, 2, 3, 4] = [0, 동, 서, 남, 북] 방향 맞춰줘야 한다
    static int[] rArr = {0, 0, 0, 1, -1};
    static int[] cArr = {0, 1, -1, 0, 0};

    public static void bfs() {
        Queue<Pair> que = new ArrayDeque<>();
        que.add(begin);
        check[begin.r][begin.c][begin.dir] = true;

        while(!que.isEmpty()) {
            Pair p = que.poll();
            int r = p.r, c = p.c, dir = p.dir, cnt = p.cnt;
            if(r == end.r && c == end.c && dir == end.dir) {
                ans = cnt;
                return;
            }

            // 현재 바라본 방향에서 1, 2, 3칸 이동 명령
            for(int i = 1; i <= 3; i++) {
                int nr = r + rArr[dir] * i;  // 현재 방향으로 i칸 이동
                int nc = c + cArr[dir] * i;
                if(1 <= nr && nr <= N && 1 <= nc && nc <= M) {  // 범위 체크
                    if(map[nr][nc] == 0 && !check[nr][nc][dir]) {
                        que.add(new Pair(nr, nc, dir, cnt + 1));
                        check[nr][nc][dir] = true;
                    }else if(map[nr][nc] == 1) {
                        break;  // 벽을 만나면 더 건너뛸 수 없음
                    }
                }
            }

            // 현재 방향을 제외한 모든 방향으로 이동
            // 180도 방향에 대해서는 +2 처리하고 나머진 +1
            for(int i = 1; i <= 4; i++) {  // i = 이동할 방향
                if(dir != i && !check[r][c][i]) {  // 현재 위치에서 방향만 도는 것임
                    int inst = 1;
                    if(dir == 1) {
                        if(i == 2) inst++;
                    }else if(dir == 2) {
                        if(i == 1) inst++;
                    }else if(dir == 3) {
                        if(i == 4) inst++;
                    }else if(dir == 4){
                        if(i == 3) inst++;
                    }
                    que.add(new Pair(r, c, i, cnt + inst));
                    check[r][c][i] = true;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N+1][M+1];
        check = new boolean[N+1][M+1][5];
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int dir = Integer.parseInt(st.nextToken());
        begin = new Pair(r, c, dir, 0);

        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        dir = Integer.parseInt(st.nextToken());
        end = new Pair(r, c, dir, 0);

        bfs();
        System.out.println(ans);
    }
}

접근법은 어렵지 않게 떠올릴 수 있었는데 구현에서 애를 먹었다.

현재 위치에서 수행할 수 있는 모든 명령을 수행해서 큐에 넣으면서 BFS를 돌리면 된다.

수행할 수 있는 명령은 아래와 같다.

1. 앞으로 이동 1 or 2 or 3칸 (3가지)

2. 현재 바라보고 있는 방향을 제외한 너머지 방향으로 방향 전환 (3가지)

이렇게 총 6가지이다.

이때 주의해야 할 점은, 방향전환에 사용되는 명령어의 개수가 모두 같지는 않다는 것이다.

한 번의 명령으로 90도만 회전할 수 있기 때문에 180도를 꺾어서 반대 방향을 보기 위해서는 두 번의 카운트를 세야 한다.

앞으로 이동하는 건 그냥 세면 되겠다만.. 이놈의 방향전환을 어떻게 해야 할지가 문제였다.

동, 서, 남 북 = 1, 2, 3, 4로 방향을 표시해야 하는데..

한 번 돌 때마다 방향을 1씩 증가or감소 시키고 1, 4에서의 증감은 4, 1로 건너뛰게 하는 식으로 하려고 했는데..

90도씩 전환하는 방향의 순서는 동쪽부터 시작한다고 했을 때 동서남북이 아니라 동남서북 순서가 되어버리기 때문이다.

그래서 동서남북 방향 1,2,3,4를 인덱스로 두고 dir = {0, 1, 3, 2, 4} 이렇게 배열의 원소를 가리키도록 짤까 했지만 이것 때문에 코드가 너무 더러워지고 헷갈려서... 결국 구글링으로 정답을 확인했다.

매번 느끼는 거지만 이런 식으로 구현능력이 부족해서 막히는 경우가 너무 많다.

로직 자체를 떠올리지 못하는 건 아닌데 이런 식으로 막히면 좌절감이 두 배가 되는 듯 하다.

방향 전환을 90도씩 할 때마다 명령을 한 번 수행한다는 점에 주목하자.

다시말해, 명령 횟수를 세는 기준을 "어느 방향으로 회전했는가?"가 아니라 "몇 도를 회전했는가?"로 잡는 것이다.

즉,

목표 방향이 동쪽이라면 이전 방향이 서쪽일 경우에 +2, 나머지는 +1

목표 방향이 서쪽이라면 이전 방향이 동쪽일 경우에 +2, 나머지는 +1

목표 방향이 남쪽이라면 이전 방향이 북쪽일 경우에 +2, 나머지는 +1

목표 방향이 북쪽이라면 이전 방향이 남쪽일 경우에 +2, 나머지는 +1

이렇게 명령 횟수를 더해주는 것이다.

풀이 2.

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

class Pair {
    int r, c, d, cnt;
    Pair(int r, int c, int d, int cnt) {
        this.r = r;
        this.c = c;
        this.d = d;
        this.cnt = cnt;
    }
}

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringBuilder sb = null;
    static StringTokenizer st = null;

    static int n, m, ans;
    static int[][] map = null;
    static boolean[][][] check = null;
    static int[] rArr = {0, 0, 0, 1, -1};  // X동서남북 맞춰줘야 함
    static int[] cArr = {0, 1, -1, 0, 0};

    static Pair start = null;
    static Pair end = null;

    public static void bfs() {
        Queue<Pair> que = new ArrayDeque<>();
        que.add(start);
        check[start.r][start.c][start.d] = true;

        while(!que.isEmpty()) {
            Pair p = que.poll();
            int r = p.r, c = p.c, d = p.d, cnt = p.cnt;
            if(r == end.r && c == end.c && d == end.d) {
                ans = cnt;
                return;
            }

            // 내 방향으로 1, 2, 3 이동
            for(int i = 1; i <= 3; i++) {
                int nr = r + rArr[d] * i;
                int nc = c + cArr[d] * i;
                if(1 <= nr && nr <= n && 1 <= nc && nc <= m) {
                    if(map[nr][nc] == 1) break;  // 벽을 만나면 더 나아갈 수 없음
                    if(!check[nr][nc][d]) {
                        check[nr][nc][d] = true;
                        que.add(new Pair(nr, nc, d, cnt+1));
                    }
                }
            }

            // 왼쪽 90도, 오른쪽 90도
            if(d == 1 || d == 2) {
                if(!check[r][c][3]) {
                    check[r][c][3] = true;
                    que.add(new Pair(r, c, 3, cnt+1));
                }
                if(!check[r][c][4]) {
                    check[r][c][4] = true;
                    que.add(new Pair(r, c, 4, cnt+1));
                }
            }else if(d == 3 || d == 4) {
                if(!check[r][c][1]) {
                    check[r][c][1] = true;
                    que.add(new Pair(r, c, 1, cnt+1));
                }
                if(!check[r][c][2]) {
                    check[r][c][2] = true;
                    que.add(new Pair(r, c, 2, cnt+1));
                }
            }
        }
    }

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n+1][m+1];
        check = new boolean[n+1][m+1][5];
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        start = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);
        st = new StringTokenizer(br.readLine());
        end = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

        bfs();
        System.out.println(ans);
    }
}

생각해보니 굳이 모든 방향으로 전부 돌기 위해 애를 쓸 필요가 없었다. 그냥 현재 위치에서 왼쪽, 오른쪽으로 한 번 씩만 돌고 마무리해도 나머지 방향으로는 그 다음 턴에서 돌아줄 테니까.

그냥 1 or 2 or 3칸 이동 3가지 경우 + 좌 or 우 90도 2가지 경우만 수행하고 다음 반복으로 넘어가면 된다.

www.acmicpc.net/problem/2206

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제 입력 1

6 4

0100

1110

1000

0000

0111

0000

예제 출력 1

15

예제 입력 2

4 4

0111

1111

1111

1110

예제 출력 2

-1

풀이 1. (틀린 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair {
    int r, c;
    Pair(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[][] map = null;
    static int[][][] path = null;
    static int N, M;
    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1, 1};

    public static void bfs() {
        Queue<Pair> que = new ArrayDeque<>();
        que.add(new Pair(0, 0));
        path[0][0][0] = 1;

        while(!que.isEmpty()) {
            Pair p = que.poll();
            int r = p.r;
            int c = p.c;

            for(int i = 0; i < 4; i++) {
                int nr = r + rArr[i];
                int nc = c + cArr[i];

                if(-1 < nr && nr < N && -1 < nc && nc < M) {
                    // 다음 좌표가 0일 때는 이전에 벽을 부쉈든 안 부쉈든 이동 가능
                    // 1. 이전에 벽을 부순 적 없고 이번에도 안 부수고 이동
                    // 2. 이전에 벽을 부순 적 있고 이번에는 안 부수고 이동

                    // 1. 이전에 벽을 부순 적 없고 이번에도 안 부수고 이동
                    if(map[nr][nc] == 0  // 벽 안 부수고 갈 수 있니?
                            && path[nr][nc][0] == N * M  // 벽 안 부수고 방문 안 했던 노드 맞니?
                            && path[r][c][1] == N * M) {  // 지금까지 벽 부순 적 없는 거 맞니?
                        path[nr][nc][0] = path[r][c][0] + 1;
                        que.add(new Pair(nr, nc));
                    }
                    // 2. 이전에 벽을 부순 적 있고 이번에는 안 부수고 이동
                    if(map[nr][nc] == 0  // 벽 안 부수고 갈 수 있니?
                            && path[nr][nc][1] == N * M  // 벽 부수고 방문 안 했던 노드 맞니?
                            && path[r][c][1] != N * M) {  // 지금까지 벽 부순 적 있는 거 맞니?
                        path[nr][nc][1] = path[r][c][1] + 1;
                        que.add(new Pair(nr, nc));
                    }

                    // 다음 좌표가 1일 때는 이전에 벽을 안 부쉈을 경우만 이동 가능
                    // 3. 이전에 벽을 안 부쉈고 이번에 부수면서 이동
                    if(map[nr][nc] == 1  // 벽 부숴야 갈 수 있는 거 맞니?
                            && path[nr][nc][1] == N * M  // 이전에 벽 부수고 방문한 적 없는 거 맞니?
                            && path[r][c][1] == N * M) {  // 지금까지 벽 부순 적 없는 거 맞니?
                        path[nr][nc][1] = path[r][c][0] + 1;  // 이번 턴에서 벽을 부숨
                        que.add(new Pair(nr, nc));
                    }
                }

            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        path = new int[N][M][2];
        for(int i = 0; i < N; i++) {
            String str = br.readLine();
            for(int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
                Arrays.fill(path[i][j], N * M);
            }
        }

        bfs();
        int ans = 0;
        if(path[N-1][M-1][0] == N*M && path[N-1][M-1][1] == N*M) {  // 이동할 수 없는 경우
            ans = -1;
        }else if(path[N-1][M-1][0] < path[N-1][M-1][1]) {
            ans = path[N-1][M-1][0];
        }else {
            ans = path[N-1][M-1][1];
        }
        System.out.println(ans);
    }
}

path[r][c][0] = (r, c)에 벽을 한 번도 부수지 않고 이동하는 최단경로

path[r][c][1] = (r, c)에 벽을 한 번만 부수고 이동하는 최단경로

이렇게 잡아두고 모든 경로를 계산하려 했다.

주어진 예제들에 대해서는 맞게 동작하는데 11%에서 틀려버린다.. 

어디가 틀린 건지 모르겠다.

세 가지 경우의 수에 대해서 쓸 데 없는 조건도 하나씩 들어가있는 거 같아서 제거해보았지만 여전히 틀린다.

풀이 2. (정답 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair {
    int r, c, cnt, destroy;
    Pair(int r, int c, int cnt, int destroy) {
        this.r = r;
        this.c = c;
        this.cnt = cnt;
        this.destroy = destroy;
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[][] map = null;
    static boolean[][][] check = null;
    static int N, M, ans = -1;
    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1, 1};

    public static void bfs() {
        Queue<Pair> que = new ArrayDeque<>();
        que.add(new Pair(0, 0, 1, 0));
        check[0][0][0] = true;

        while(!que.isEmpty()) {
            Pair p = que.poll();
            int r = p.r;
            int c = p.c;
            int cnt = p.cnt;
            int destroy = p.destroy;

            if(r == N - 1 && c == M - 1) {
                ans = cnt;
                return;
            }

            for(int i = 0; i < 4; i++) {
                int nr = r + rArr[i];
                int nc = c + cArr[i];

                if(-1 < nr && nr < N && -1 < nc && nc < M) {
                    if(map[nr][nc] == 1) {  // 벽이면??
                        if(destroy == 0 && !check[nr][nc][1]) {  // 이전에 부순적 없으면 부수고 이동
                            que.add(new Pair(nr, nc, cnt + 1,  destroy + 1));
                            check[nr][nc][destroy+1] = true;
                        }
                    }else{  // 벽이 아니면??
                        if(!check[nr][nc][destroy]) {  // 현재 destroy 횟수로 다음 좌표 갈 수 있는지만
                            que.add(new Pair(nr, nc, cnt + 1, destroy));  // destroy 유지하면서 이동
                            check[nr][nc][destroy] = true;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        check = new boolean[N][M][2];
        for(int i = 0; i < N; i++) {
            String str = br.readLine();
            for(int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        bfs();
        System.out.println(ans);
    }
}

check와 cnt를 하나의 배열로 관리하고 싶어서 path[][][]를 사용했던 건데 오히려 그것 때문에 더 헷갈리게 된 거 같다. 코드도 지저분했고.

Pair 안에 cnt와 destroy(지금까지 벽 부순 횟수)를 포함하도록 짰더니 훨씬 깔끔해졌다.

EntityManager를 사용해 작업을 수행해도 commit을 하기 전까지는 작업의 결과들이 DB에 반영되지 않는다고 했었다.

정확히는 "Flush가 호출되기 전에는 DB에 반영되지 않는다"가 맞다.

Flush가 호출되면 영속성 컨텍스트 안에 보관되고있던 이전 작업들에 대한 결과가 실제 DB에 반영이 된다.

(영속성 컨텍스트를 비우는 것이 아니라 영속성 컨텍스트의 변경내용을 DB에 적용시켜 주는 것이다)

영속성 컨텍스트를 Flush하는 방법은 세 가지가 존재한다.

(사실 실전에서 직접적으로 도움이 되는 내용은 아니지만 테스트 등에서 사용될 수 있다)

1. em.flush()

-> 그냥 직접 호출하는 것이다.

2. transaction.commit()

-> 트랜잭션 커밋을 수행하면 플러시가 자동으로 호출된다.

3. JPQL

-> JPQL 쿼리를 실행하면 플러시가 자동으로 호출된다.

-> JPQL은 SQL로 번역되어 DB에 바로 접근하게 된다. 이 경우에 만약 영속성 컨텍스트의 내용이 DB에 적용되지 않은 상태로 JPQL이 수행된다면 문제가 발생할 수 있으므로 JPQL 전에는 항상 flush를 먼저 수행한다.

영속성 컨텍스트의 생존 범위는 반드시 트랜잭션과 함께 동작하도록 해야 한다.

스프링 프레임워크를 사용하면 스프링에 의해 트랜잭션이 종료될 때 영속성 컨텍스트도 함께 종료되도록 동작한다.

JPA는 왜 Java "Persistence" API인가? 바로 Persistence Context를 사용하기 때문.

맨 처음 웹 애플리케이션이 실행되면 EntityManagerFactory라는 녀석이 생성되고 그 후 사용자의 요청이 들어올 때마다 각각의 EntityManager를 만들어서 요청을 수행한다.

Persistence Context (영속성 컨텍스트)는 이 EntityManager안에 들어있는 녀석인데 이것이 자바 코드와 DB 사이에서 중간자 역할을 한다.

굳이 의미를 풀자면 "엔티티를 영구적으로 저장하는 환경" 정도가 된다.

객체를 엔티티로서 디비에 저장하거나 디비의 엔티티를 객체로 가져오는 명령을 내릴 때 해당 엔티티틑 영속성 컨텍스트 안에 존재하고 있다가 트랜잭션 커밋이 이뤄질 때 쿼리를 DB에 전달하여 동작을 완전히 수행한다.

이러한 영속성 컨텍스트 안에서 엔티티는 네 가지 생명주기를 갖는다.

1. 비영속 (new / transient)

-> 영속성 컨텍스트와 전혀 관계가 없는 상황. 새로 생성한 객체를 em.persist() 하기 전 이 객체는 '비영속' 상태에 해당된다.

2. 영속성 (managed)

-> 영속성 컨텍스트 안에서 관리되고 있는 상태. em.persist()를 하고난 이후의 객체가 '영속성' 상태에 해당된다.

3. 준영속 (detached)

-> 영속성 컨텍스트 안에 존재하다가 분리된 상태. em.persist(member)로 영속성 컨텍스트 안에 들어갔다가 em.detach(member)로 다시 분리하면 이때의 상태가 '준영속' 상태에 해당된다.

4. 삭제 (removed)

-> 객체를 완전히 삭제한 상태. 영속성 컨텍스트 안에 존재하는 객체에 대해 em.remove(member)하여 객체를 삭제하면 이 때의 상태가 '삭제' 상태이다.

비영속 상태와 준영속 상태는 같은 것이 아닌가 싶었는데 그에 대한 해답을 아래 링크에서 찾을 수 있었다.

www.inflearn.com/questions/45195      

영속성 컨텍스트 안에는 1차 캐시가 존재하여 캐싱을 지원한다.

그렇긴 한데 이게 실제 상황에서 그렇게 큰 시간절약을 이루어주지는 않는다고 한다.

단 건에 대한 기본적인 CRUD 기능은 아래와 같이 간편하게 사용할 수 있었다.

        EntityManager em = emf.createEntityManager();
        EntityTransaction tx = em.getTransaction();
        tx.begin();

        Member member = new Member();
        member.setId(1L);
        member.setName("name1");
        
        // Create
        em.persist(member);  // list.add(Object o) 처럼 간편하게 DB에 객체 저장
        // Read
        Member findMember = em.find(Member.class, 1L);  // PK를 사용하여 간편하게 읽어옴
        // Update
        findMember.setName("change name");  // 조회한 객체에 대하여 수정을 하는 것만으로 update쿼리까지 완료됨
        // Delete
        em.remove(member);  // 조회한 객체를 삭제하면 테이블에서도 해당 엔티티 바로 삭제됨

        tx.commit();

그럼 좀 더 복잡한 경우에 대해서는 어떻게 해야할까? 

여러 개의 행을 반환해야 하거나 검색 조건을 넣어 조회를 해야한다면?

이런 경우에는 약간의 쿼리 작성이 필요하다. 하지만 DB 테이블을 기준으로 쿼리를 작성하지 않는다.

그게 무슨 말이지?

->

JPA의 존재 의의는 DB 테이블에 종속되지 않고 엔티티 객체 중심적으로 개발을 하기 위함이다.

그렇기에 부득이하게 쿼리를 짜야하는 일이 있어도 객체에 초점을 맞춰 쿼리를 작성한다.

만약 실제 물리적 DB에 맞춰 쿼리를 짠다면 그것은 DB에 종속적인 설계가 되는 것이고 이는 JPA의 사용 취지에 어긋난다.

// 여러 건의 검색 결과를 List에 담아 반환한다.
List<Member> result = em.createQuery("select m from Member as m", Member.class).getResultList();

위와 같은 문제를 해결하기 위해 JPA는 SQL을 추상화한 JPQL이라는 객체 지향 쿼리 언어를 제공한다.

쿼리를 자세히 보면 지금까지 작성했던 쿼리와의 차이점을 알 수 있다.

from table_name이 아닌 from class_name의 형식으로 작성된 쿼리이다.

이런식으로 객체 중심적으로 쿼리를 작성하면 이 역시 JPA가 Member클래스에 해당하는 테이블명에 대한 쿼리를 알아서 날려서 조회를 해준다.

이렇게 객체 중심적으로 작성하는 쿼리를 JPQL(Java Persistence Query Language)라고 한다.

JPQL은 SELECT, FROM, WHERE, GROUP BY, HAVING, JOIN을 지원한다.

요즘은 NoSQL도 많이 사용한다지만 아직 가장 보편적인 데이터베이스는 RDB(Relational Database)이다.

객체지향 프로그래밍을 하면서 생성한 도메인 객체들은 관계형 데이터베이스에 저장되어서 관리된다.

즉, 도메인 클래스가 DB의 테이블과 대응되고 해당 클래스의 객체는 테이블의 엔티티로서 저장되는 것이다.

이를 위해서는 RDB 테이블에 해당 객체를 매핑(Mapping)시켜줘야 한다.

이를 ORM(Object Relational Mapping)이라고 한다.

고대(?) 자바 개발에서는 이 모든 작업을 JDBC를 통해 처리했다.

그런데 이 방법은 드라이버를 연결하고 SQL을 문자열로 하나하나 직접 작성하는 기계적이고 반복적인 작업에 소요되는 시간이 너무나 컸다.

너무나도 불필요한 낭비였지만 다른 대안이 없었기에 불가피했다.

또한 아무리 객체를 RDB에 매핑하여 저장한다지만 이 둘이 상속, 연관관계, 데이터 타입, 데이터 식별 방법 등 본질적인 패러다임까지 완전히 같은 것은 아니기에 여러 가지 문제들이 발생했다.

이런 배경 속에 등장한 것이 JPA(Java Persistence API)이다.

JPA는 객체를 마치 자바 Collections에 저장해 관리하는 것처럼 편리하게 DB에 저장할 수 있도록 해주는 ORM 프레임워크이다.

RDB는 RDB대로 그 특성에 맞게 설계하고 객체는 객체대로 설계한다. 사용자는 편하게 객체를 저장하고 귀찮은 매핑 작업은 전부 JPA가 처리한다.

즉, 패러다임의 불일치에 대해서 신경쓰지 않고 작업하는 것이다.

하지만 내부적으로는 여전히 JDBC가 사용된다. 사용자가 직접 사용하진 않게 되었지만 사용자 편하게 내린 명령을 JPA가 이전까지 해왔던 JDBC를 사용한 그런 복잡한 과정들을(SQL을 하나하나 작성하는 등) 거쳐 RDB에 매핑해주는 것이다.

기본적인 CRUD 기능에 대한 쿼리는 내부적으로 JPA가 전부 알아서 짜주기 때문에 더 이상 기계적, 반복적인 SQL 작업에 오랜 시간 고통받을 필요가 없어졌다.

JPA는 인터페이스의 모음이고 그것을 상속한 클래스가 여러 가지 존재하지만 hibernate가 대표적으로 사욯된다.

아래와 같은 방식으로 가장 기본적인 CRUD 기능을 쿼리 작성 없이 간단하게 사용할 수 있다.

        EntityManager em = emf.createEntityManager();
        EntityTransaction tx = em.getTransaction();
        tx.begin();

        Member member = new Member();
        member.setId(1L);
        member.setName("name1");
        
        // Create
        em.persist(member);  // list.add(Object o) 처럼 간편하게 DB에 객체 저장
        // Read
        Member findMember = em.find(Member.class, 1L);  // PK를 사용하여 간편하게 읽어옴
        // Update
        findMember.setName("change name");  // 조회한 객체에 대하여 수정을 하는 것만으로 update쿼리까지 완료됨
        // Delete
        em.remove(member);  // 조회한 객체를 삭제하면 테이블에서도 해당 엔티티 바로 삭제됨

        tx.commit();

그런데, 위의 CRUD는 모두 하나의 객체에 대한 작업이다.

그럼 특정 조건의 엔티티 여러 개를 조회해야 하는 등 더 복잡한 경우엔 어떻게 할까?

이것을 위한 JPQL을 이 다음 글에서 설명한다.