N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.
지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
지붕의 가장자리는 땅에 닿아야 한다.
비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.
그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.
그림1 . 기둥과 지붕(굵은 선)의 예
창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.
기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.
입력
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.
출력
첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.
예제 입력 1
7
24
114
158
46
53
810
136
예제 출력 1
98
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
import java.util.StringTokenizer;
class Pillar implements Comparable<Pillar>{
int left;
int height;
Pillar(int left, int height) {
this.left = left;
this.height = height;
}
@Override
public int compareTo(Pillar o) {
return this.left < o.left ? -1 : 1;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
Stack<Pillar> leftStk = new Stack<>();
Stack<Pillar> rightStk = new Stack<>();
ArrayList<Pillar> pillars = new ArrayList<>();
int n = Integer.parseInt(br.readLine());
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int L = Integer.parseInt(st.nextToken());
int H = Integer.parseInt(st.nextToken());
pillars.add(new Pillar(L, H));
}
Collections.sort(pillars); // 입력 순서 보장되지 않는다. 정렬 필요
// 가운데의 가장 높은 기둥을 기준으로 left, right 스택 채운다. 단, 높이가 증가하는 기둥만 채운다
int maxHeight = 0;
int len = pillars.size();
for(int i = 0; i < len; i++) {
if(maxHeight < pillars.get(i).height) {
maxHeight = pillars.get(i).height;
leftStk.push(pillars.get(i));
}
}
maxHeight = 0;
for(int i = len - 1; i >= 0; i--) {
if(maxHeight < pillars.get(i).height) {
maxHeight = pillars.get(i).height;
rightStk.push(pillars.get(i));
}
}
int ans = (rightStk.peek().left - leftStk.peek().left + 1) * rightStk.peek().height;
int beforeLeft = leftStk.pop().left;
while(!leftStk.isEmpty()) {
int left = leftStk.peek().left;
int height = leftStk.peek().height;
ans += (beforeLeft - left) * height;
beforeLeft = left;
leftStk.pop();
}
int beforeRight = rightStk.pop().left + 1;
while(!rightStk.isEmpty()) {
int right = rightStk.peek().left + 1;
int height = rightStk.peek().height;
ans += (right - beforeRight) * height;
beforeRight = right;
rightStk.pop();
}
System.out.println(ans);
}
}
처음 봤을 때는 문제의 그림을 보고 이차원 배열을 탐색하는 그래프 문제라고 생각했다.
DFS, BFS 문제를 너무 많이 풀다 보니까 일단 무작정 그런 쪽으로 생각하게 되는 거 같다.
정말 대놓고 보이는 게 아닌 이상은 항상 어떤 어떤 알고리즘을 적용시키는 게 좋을지를 먼저 생각해보자.
스택으로 분류 되어있지만 딱히 스택일 필요는 없는 문제. 그냥 어레이리스트를 사용해도 된다.
창고다각형은 가장 높은 기둥을 가운데에 두고 그 양 옆으로 높이가 점점 내려가는 모양을 띄게 된다.
가장 높은 기둥을 중앙일 때,
왼쪽 부분에서는 높이가 점점 올라가는 기둥들만,
오른쪽 부분에서는 높이가 점점 내려가는 기둥들만 따로 모은다.
그 후 넓이를 계산해주면 된다.
주의할 점은, 가운데에 오는 가장 높은 기둥이 여러 개일 경우를 대비하여 이것도 따로 계산해줘야 한다는 것이다.
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.
출력
총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.
예제 입력 1
3
0 10
001
100
예제 출력 1
111
111
111
예제 입력 2
7
0001000
0000001
0000000
0000110
1000000
0000001
0 010000
예제 출력 2
1011111
0010001
0000000
1011111
1011111
0010001
0010000
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int[][] map = null;
static int[][] ans = null;
static int n;
public static void dfs(int start, int now) {
for(int next = 0; next < n; next++) {
if(map[now][next] == 1 && ans[start][next] == 0) { // ans로 방문 여부 체크
ans[start][next] = 1;
dfs(start, next);
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new int[n][n];
ans = new int[n][n];
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(map[i][j] == 1 && ans[i][j] == 0) {
ans[i][j] = 1;
dfs(i, j);
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
System.out.print(ans[i][j] + " ");
}
System.out.println();
}
}
}
단방향 그래프의 탐색 문제.
항상 좌표로 표시되는 맵에서 양방향 그래프 탐색으로만 풀다가 단방향을 풀려니 좀 헷갈렸다.
이 문제는 탐색 점을 row, col으로 표시를 하는 것은 부적절하며 시작점을 계속 가지고 있어야 한다.
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.
초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.
위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.
사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.
위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다.
입력
사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.
첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)
둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.
가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.
가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.
입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.
출력
i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.
예제 입력 1
203
예제 출력 1
0
예제 입력 2
213
11
예제 출력 2
1
예제 입력 3
556
11
32
23
51
54
예제 출력 3
3
예제 입력 4
656
11
32
13
25
55
예제 출력 4
3
예제 입력 5
586
11
22
33
44
31
42
53
64
예제 출력 5
-1
예제 입력 6
5126
11
13
22
24
31
33
42
44
51
53
62
64
예제 출력 6
-1
예제 입력 7
566
11
31
52
43
23
14
예제 출력 7
2
풀이 1. (틀린 코드 - 시간 초과)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int n, h, m, ans = -1;
static int[][] map = null;
static boolean[][] check = null;
// 위는 검사하지 않는다. 양 옆에 1 있는지 먼저 체크. 없으면 아래로
static int[] rArr = {0, 0}; // 좌 우
static int[] cArr = {-1 ,1}; // 좌 우
public static boolean isPossible() {
// i열이 i열로 도작하는지 체크
// 여기서 결국 탐색 한 번 다 돌려야 할 듯?
for(int i = 1; i <= n; i++) {
check = new boolean[h+2][n+1]; // 가로선 계속 타는 무한루프 막기 위한 체킹
check[1][i] = true;
int endCol = search(1, i);
if(endCol != i) {
return false;
}
}
return true;
}
public static int search(int r, int c) {
// 내가 1이면 내 오른쪽 열로 이동
// 내 왼쪽이 1이면 내 왼쪽으로 이동
// 내 아래 행으로는 항상 이동 가능 (우선순위는 열 이동에 있음)
// 가로선은 H행이 끝이지만 완료 검사는 H+1행에서 해야 한다
if(r == h+1) { // 끝에 도착했으면 시작과 동일한지 체크
int endCol = c;
return endCol;
}
for(int i = 0; i < 2; i++) { // 좌우 검사
int nr = r + rArr[i];
int nc = c + cArr[i];
if(0 < nr && nr <= h && 0 < nc && nc <= n && !check[nr][nc]) { // H행 N열 범위 체크
if(i == 0 && map[nr][nc] == 1) { // 좌
check[nr][nc] = true;
check[nr+1][nc] = true; // 어차피 연속으로 열 이동 불가. 열 이동한 이후엔 어차피 아래로 가야함
return search(nr+1, nc);
}
if(i == 1 && map[r][c] == 1) { // 우
check[nr][nc] = true;
check[nr+1][nc] = true;
return search(nr+1, nc);
}
}
}
check[r+1][c] = true;
return search(r+1, c); // 하
}
public static void dfs(int r, int c, int deptNow, int dept) {
if(isPossible()){
if(ans == -1) {
ans = deptNow;
}else {
ans = Math.min(ans, deptNow);
}
return;
}
if(deptNow == dept) {
return;
}
// 이제 여기서 가로실선을 하나씩 놓자
for(int i = r; i <= h; i++) { // 이전 행은 다시 확인할 필요 없음
for(int j = 1; j < n; j++) { // 마지막 열에는 놓을 수 없다
// 0열은 사용하지 않는 열이고 n열은 애초에 1이 올 수 없는 열이므로 범위 문제 없음
if(map[i][j] == 0 && map[i][j-1] == 0 && map[i][j+1] == 0) {
map[i][j] = 1;
dfs(i, j, deptNow + 1, dept);
map[i][j] = 0;
}
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine()); // N, M, H 순 입력
// N : 세로 실선 (2 ~ 20)
// H : 가로 점선 (1 ~ 30)
// M : 가로 실선
// H행 N열
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
map = new int[h+2][n+1];
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
map[a][b] = 1;
}
dfs(1, 1, 0, m);
System.out.println(ans > 3 ? -1 : ans);
}
}
시간 초과 코드이지만 일단 예제 입력은 전부 잘 돌아간다.
이걸 짜는 것만 해도 2시간이 걸렸다;
로직은 이렇다.
백트래킹을 하면서 가로 선을 하나씩 놓는다.
가로선의 최소 개수를 구하는 것이므로 하나 놓을 때마다 맵을 탐색하여 검사한다.
isPossible()에서는 각 열을 시작점으로 하여 n번의 탐색을 실시해야 한다. (도중에 하나라도 false가 뜨면 바로 리턴 한다)
값이 1인 좌표는 해당 좌표의 오른쪽 열로 넘어갈 수 있다는 뜻.
그러므로 탐색을 할 때는 내 좌표가 1인지, 내 왼쪽 좌표가 1인지를 모두 검사해야 한다. 오->왼 이동도 가능하기 때문.
연속된 가로선은 있을 수 없다는 조건이기 때문에 가로 이동을 실시하는 경우 바로 그 아래칸까지 보내버려도 된다.,
가로 이동이 불가할 경우 세로 이동만 실시.
주의할 점은 도착 검사를 h행이 아닌 h+1 행에서 해야 한다는 것이다. h행에서도 다른 열로 이동할 수도 있기 때문이다.
백트래킹하며 가로선을 하나씩 놓는 부분에서 시간 초과를 막기 위해 재귀 후 다음 탐색은 r행부터 실시하도록 했지만 시간 초과를 막는 데는 역부족이었다. 결국 시간 초과..
풀이 2. (정답 코드 - 3276ms)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int n, h, m, ans = -1;
static int[][] map = null;
static boolean[][] check = null;
static boolean complete;
// 위는 검사하지 않는다. 양 옆에 1 있는지 먼저 체크. 없으면 아래로
static int[] rArr = {0, 0}; // 좌 우
static int[] cArr = {-1 ,1}; // 좌 우
public static boolean isPossible() {
// i열이 i열로 도작하는지 체크
// 여기서 결국 탐색 한 번 다 돌려야 할 듯?
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= h+1; j++) {
Arrays.fill(check[j], false); // 가로선 계속 타는 무한루프 막기 위한 체킹
}
check[1][i] = true;
int endCol = search(1, i);
if(endCol != i) {
return false;
}
}
return true;
}
public static int search(int r, int c) {
// 내가 1이면 내 오른쪽 열로 이동
// 내 왼쪽이 1이면 내 왼쪽으로 이동
// 내 아래 행으로는 항상 이동 가능 (우선순위는 열 이동에 있음)
// 가로선은 H행이 끝이지만 완료 검사는 H+1행에서 해야 한다
if(r == h+1) { // 끝에 도착했으면 시작과 동일한지 체크
int endCol = c;
return endCol;
}
for(int i = 0; i < 2; i++) { // 좌우 검사
int nr = r + rArr[i];
int nc = c + cArr[i];
if(0 < nr && nr <= h && 0 < nc && nc <= n && !check[nr][nc]) { // H행 N열 범위 체크
if(i == 0 && map[nr][nc] == 1) { // 좌
check[nr][nc] = true;
check[nr+1][nc] = true; // 어차피 연속으로 열 이동 불가. 열 이동한 이후엔 어차피 아래로 가야함
return search(nr+1, nc);
}
if(i == 1 && map[r][c] == 1) { // 우
check[nr][nc] = true;
check[nr+1][nc] = true;
return search(nr+1, nc);
}
}
}
check[r+1][c] = true;
return search(r+1, c); // 하
}
public static void dfs(int r, int c, int deptNow, int dept) {
if(complete) return;
if(deptNow == dept) {
if(isPossible()) {
ans = deptNow; // dept는 1~3 순서로 올라가므로 굳이 대소비교 하지 않고 바로 넣어도 된다
complete = true;
}
return;
}
// 이제 여기서 가로실선을 하나씩 놓자
for(int i = r; i <= h; i++) { // 이전 행은 다시 확인할 필요 없음
for(int j = 1; j < n; j++) { // 마지막 열에는 놓을 수 없다
// 0열은 사용하지 않는 열이고 n열은 애초에 1이 올 수 없는 열이므로 범위 문제 없음
if(map[i][j] == 0 && map[i][j-1] == 0 && map[i][j+1] == 0) {
map[i][j] = 1;
dfs(i, j, deptNow + 1, dept);
map[i][j] = 0;
}
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine()); // N, M, H 순 입력
// N : 세로 실선 (2 ~ 20)
// H : 가로 점선 (1 ~ 30)
// M : 가로 실선
// H행 N열
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
map = new int[h+2][n+1];
check = new boolean[h+2][n+1];
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
map[a][b] = 1;
}
for(int i = 0; i <= 3; i++) {
dfs(1, 1, 0, i);
if(complete)
break;
}
System.out.println(ans);
}
}
무작정 가로선 하나를 놓을 때마다 검사를 한 번 씩 하는 게 문제였다.
목표 dept를 1~3으로 두고 목표 dept에 달성할 때까지는 그냥 놓기만 한 다음 다 놓고서 검사를 하는 방식으로 고쳤다.
정답이 3보다 클 경우 -1을 출력해야하므로 dept는 3까지만 해보면 된다.
처음으로 나오는 정답이 최소값이기 때문에 그 이후엔 재귀나 반복을 더 들어가지 않고 탈출하도록 boolean complete를 사용했다.
통과하긴 했지만 아직도 너무 느리다. (3276ms)
풀이 3. (정답 코드 - 428ms)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int n, h, m, ans = -1;
static int[][] map = null;
static boolean complete;
public static boolean isPossible() {
for(int i = 1; i <= n; i++) { // 모든 열 검사
int r = 1;
int c = i;
for(int j = 1; j <= h; j++) {
if(map[r][c-1] == 1) { // 왼쪽 이동 가능?
c -= 1;
r += 1;
continue;
}
if(map[r][c] == 1) { // 오른쪽 이동 가능?
c += 1;
r += 1;
continue;
}
r += 1; // 양 옆 이동 불가면 아래로 이동
}
if(c != i) return false;
}
return true;
}
public static void dfs(int r, int c, int deptNow, int dept) {
if(complete) return;
if(deptNow == dept) {
if(isPossible()) {
ans = deptNow; // dept는 1~3 순서로 올라가므로 굳이 대소비교 하지 않고 바로 넣어도 된다
complete = true;
}
return;
}
// 이제 여기서 가로실선을 하나씩 놓자
for(int i = r; i <= h; i++) { // 이전 행은 다시 확인할 필요 없음
for(int j = 1; j < n; j++) { // 마지막 열에는 놓을 수 없다
// 0열은 사용하지 않는 열이고 n열은 애초에 1이 올 수 없는 열이므로 범위 문제 없음
if(map[i][j] == 0 && map[i][j-1] == 0 && map[i][j+1] == 0) {
map[i][j] = 1;
dfs(i, j, deptNow + 1, dept);
map[i][j] = 0;
}
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine()); // N, M, H 순 입력
// N : 세로 실선 (2 ~ 20)
// H : 가로 점선 (1 ~ 30)
// M : 가로 실선
// H행 N열
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
map = new int[h+2][n+1];
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
map[a][b] = 1;
}
for(int i = 0; i <= 3; i++) {
dfs(1, 1, 0, i);
if(complete)
break;
}
System.out.println(ans);
}
}
시간이 확 줄어들었다.
가로선을 다 놓은 후 검사하는 방식에 문제가 있었다.
검사 코드를 너무 DFS 식으로 짜버려서 생긴 문제였다.
굳이 재귀와 check배열을 사용해가며 탐색할 필요 없다.
그냥 간단한 인덱스 조작을 통해 빠르게 검사할 수 있었다.
매번 check배열을 초기화하는 부분도 너무 시간낭비였는데 check 자체가 필요없어지니 속도도 빨라졌다.
n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-)
이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.
입력
첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.
예제 입력 1
4
1491210
11154
715213
63168
예제 출력 1
4
풀이 1. (틀린 코드 - 메모리 초과)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int n, ans;
static int[][] map = null;
static int[][][] dp = null; // dp[r][c][dept] = (r, c)에 dept번째로 방문했을 때 가질 수 있는 최장경로
static int[] rArr = {-1, 1, 0, 0};
static int[] cArr = {0, 0, -1 ,1};
public static void dfs(int r, int c, int dept) {
dp[r][c][dept] = 0;
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 < n && map[r][c] < map[nr][nc]) {
if(dp[nr][nc][dept+1] == -1) {
dfs(nr, nc, dept+1);
}
dp[r][c][dept] = Math.max(dp[r][c][dept], dp[nr][nc][dept+1]); // 상하좌우 중 최대값
}
}
dp[r][c][dept] += 1; // 자기 자신에 대한 값 추가
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new int[n][n];
dp = new int[n][n][n*n];
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// dp 초기화
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
Arrays.fill(dp[i][j], -1);
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
dfs(i, j, 0);
ans = Math.max(ans, dp[i][j][0]);
}
}
System.out.println(ans);
}
}
로직은 맞지만 메모리 초과가 나는 코드.
매번 풀기 전에 시간, 용량 계산부터 해보자고 다짐하면서도 그걸 실행에 옮기기가 쉽지 않다.
n제한이 dp를 3차원 배열로 사용할 경우 500^4 칸의 int 배열이 필요한데 이는 약 250GB의 용량.. 메모리 제한 256MB를 넘어가도 한참을 넘어간다.
로직은 이랬다.
dp[r][c][dept] = (r, c)를 dept번째로 방문했을 때 더 나아갈 수 있는 최장경로.
(r, c)에서 상하좌우의 (nr, nc)에 대해 dp[nr][nc][dept+1]의 값 중 최대값을 더한 후 자신에 대한 값 1을 추가하는 것이다.
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.
오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.
파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.
파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.
파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.
파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.
아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.
가로
세로
대각선
가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.
입력
첫째 줄에 집의 크기 N(3 ≤ N ≤ 32)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.
출력
첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다.
예제 입력 1
3
000
000
000
예제 출력 1
1
예제 입력 2
4
0000
0000
0000
0000
예제 출력 2
3
예제 입력 3
5
00100
00000
00000
00000
00000
예제 출력 3
0
예제 입력 4
6
000000
010000
000000
000000
000000
000000
예제 출력 4
13
예제 입력 5
22
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
0000000000000000000000
예제 출력 5
4345413252
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] map = new int[n][n];
long[][][] dp = new long[n][n][3]; // 0=가로, 1=세로, 2=대각
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());
}
}
dp[0][1][0] = 1; // 최초 상태
for(int i = 0; i < n; i++) {
for(int j = 2; j < n; j++) {
if(j - 1 >= 0 && map[i][j] == 0) { // 가로
dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2];
}
if(i - 1 >= 0 && map[i][j] == 0) { // 세로
dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2];
}
if(i-1 >= 0 && j-1 >= 0 && map[i][j] == 0 && map[i-1][j] == 0 && map[i][j-1] == 0) { // 대각
dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2];
}
}
}
long ans = dp[n-1][n-1][0] + dp[n-1][n-1][1] + dp[n-1][n-1][2];
System.out.println(ans);
}
}
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.
오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.
파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.
파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.
파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.
파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.
아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.
가로
세로
대각선
가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.
입력
첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.
출력
첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.
예제 입력 1
3
000
000
000
예제 출력 1
1
예제 입력 2
4
0000
0000
0000
0000
예제 출력 2
3
예제 입력 3
5
00100
00000
00000
00000
00000
예제 출력 3
0
예제 입력 4
6
000000
010000
000000
000000
000000
000000
예제 출력 4
13
풀이 1. (DP)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] map = new int[n][n];
int[][][] dp = new int[n][n][3]; // 0=가로, 1=세로, 2=대각
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());
}
}
dp[0][1][0] = 1; // 최초 상태
for(int i = 0; i < n; i++) {
for(int j = 2; j < n; j++) {
if(j - 1 >= 0 && map[i][j] == 0) { // 가로
dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2];
}
if(i - 1 >= 0 && map[i][j] == 0) { // 세로
dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2];
}
if(i-1 >= 0 && j-1 >= 0 && map[i][j] == 0 && map[i-1][j] == 0 && map[i][j-1] == 0) { // 대각
dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2];
}
}
}
int ans = dp[n-1][n-1][0] + dp[n-1][n-1][1] + dp[n-1][n-1][2];
System.out.println(ans);
}
}
디피디피디피디피디피 이놈의 디피..
처음 문제를 봤을 때는 예제 그림 때문에 새로운 파이프를 하나씩 놓는 것으로 착각하였다.
45도만 회전이 가능하다는 조건도 조금 모호한 부분이 있지 않나 싶다.
DP 문제는 언제나 어떤 값을 메모이제이션 할 것인지가 가장 중요하다.
dp[r][c][stat] = 파이프 (r, c)을 끝점으로 하며 stat 상태로 존재할 수 있는 경우의 수
stat : 가로=0, 세로=1, 대각=2
각 방향으로 파이프를 옮길 수 있는 경우는 아래와 같다.
1. 가로 방향으로 파이프를 놓음
-> 왼쪽 칸에서 가로, 대각일 때만 가능
2. 세로 방향으로 파이프를 놓음
-> 위쪽 칸에서 세로, 대각일 때만 가능
3. 대각 방향으로 파이프를 놓음
-> 왼쪽 위 칸에서 가로, 세로, 대각일 때 모두 가능
풀이 2. (DFS or BFS)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int n, ans;
static int[][] map = null;
static int[] rArr = {-1, 1, 0, 0};
static int[] cArr = {0, 0, -1 ,1};
public static void dfs(int r, int c, int dir) {
if(r == n-1 && c == n-1) {
ans += 1;
return;
}
if(dir == 0) { // 가로, 대각 이동 가능
if(c+1 < n && map[r][c+1] == 0) {
dfs(r, c+1, 0);
}
if(r+1 < n && c+1 < n && map[r+1][c] == 0 && map[r][c+1] == 0 && map[r+1][c+1] == 0) {
dfs(r+1, c+1, 2);
}
}else if(dir == 1) { // 세로, 대각 이동 가능
if(r+1 < n && map[r+1][c] == 0) {
dfs(r+1, c, 1);
}
if(r+1 < n && c+1 < n && map[r+1][c] == 0 && map[r][c+1] == 0 && map[r+1][c+1] == 0) {
dfs(r+1, c+1, 2);
}
}else { // 가로, 세로, 대각 이동 가능
if(c+1 < n && map[r][c+1] == 0) {
dfs(r, c+1, 0);
}
if(r+1 < n && map[r+1][c] == 0) {
dfs(r+1, c, 1);
}
if(r+1 < n && c+1 < n && map[r+1][c] == 0 && map[r][c+1] == 0 && map[r+1][c+1] == 0) {
dfs(r+1, c+1, 2);
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new int[n][n];
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0, 1, 0);
System.out.println(ans);
}
}
사실 처음에 DFS로 짰다가 틀려서 정답을 확인하고 DP로 짰던 건데.. DFS로도 짤 수 있었다.
습관적으로 check 배열을 사용했는데 이 부분이 문제였다.
나름대로 머리를 쓴다고 3차원 배열을 사용해서 각 상태마다 해당 좌표에서 존재한 적이 있는지 따로 검사를 했었는데..
그냥 검사 자체를 하면 안 된다.
어떤 좌표에 어떤 상태로 존재한 적이 있었다고 해도 그 좌표까지 도달하기 위한 경로가 다를 수 있기 때문이다.
그 부분만 고쳐줬더니 바로 통과되었다.
탐색 조건 부분에서 DP와 DFS의 차이는, DP는 현재 위치로 오기 전 위치에 어떤 상태로 존재할 수 있는지를 검사하는 것이고 DFS는 현재 위치에서 다음 위치로 어떤 상태로 이동할 수 있는지를 검사하는 것이다.
이전에 말했듯이 JPA는 객체와 DB의 패러다임 불일치로 인한 불편을 없애고 객체를 마치 Collections에 저장하는 것처럼 DB에 저장할 수 있게 하기 위해서 등장했다.
개발을 하다보면 필연적으로 연관관계를 가진 테이블들이 존재할 수밖에 없게 되는데 이에 대해선 어떻게 처리해야 할까?
N : 1의 관계로 이루어진 Member와 Team이 있다고 하자. 하나의 Team에 여러 Member가 소속될 수 있고 이러한 관계를 나타내기 위해 Member가 Team의 PK를 FK로 가지게 될 것이다.
이러한 방식을 따라 클래스를 설계하면 아래와 같은 형태가 된다.
@Entity
public class Member {
@Id @GeneratedValue
@Column(name = "MEMBER_ID")
private Long id;
@Column(name = "USERNAME")
private String name;
@Column(name = "TEAM_ID")
private Long teamId;
}
그런데 이는 DB에 종속적으로 맞춘 설계이다. 즉, 객체 지향적인 설계라고 볼 수 없다.
위와 같이 설계를 한다면 em.find(memberId) 로 member를 찾고, member.getTeamId()를 통해 teamId를 찾고 다시 그걸 이용해 em.find(teamId)로 해당 멤버가 속한 팀을 찾아야 한다.
하지만 여태껏 자바 프로그래밍을 해왔던 대로라면 Member 안에 Team 객체에 대한 변수를 두어 참조 관계를 형성하고 member에서 바로 Team 객체에 접근하도록 하는 것이 우리가 지금까지 해왔던 객체지향적인 설계이다.
앞서 언급했다시피 JPA는 이러한 패러다임 불일치를 없애고 객체 지향적인 설계에 집중할 수 있도록 도와주는 도구이다.
아래와 같은 방법으로 객체 지향적인 모델링을 할 수 있다.
@Entity
public class Member {
@Id @GeneratedValue
@Column(name = "MEMBER_ID")
private Long id;
@Column(name = "USERNAME")
private String name;
@ManyToOne
@JoinColumn(name = "TEAM_ID")
private Team team;
}
참조 관계처럼 Member가 Team team을 직접 소유한다. 그리고 @ManyToOne을 통해 Member : Team의 N : 1 관계를 표현한 후 @JoinColumn을 통해 DB 내에서 Member 테이블이 FK로 가질 Team 테이블의 PK를 지정해준다.
위와 같은 방식의 연관관계 매핑을 '단방향 연관관계'라고 한다. Member는 참조 변수 team을 통해 자신이 속한 Team에 접근이 가능하지만 Team에선 자신에게 속한 Member들에 접근이 불가하기 때문에 단방향이라는 이름이 붙었다.
그런데 일반적인 관계형 데이터베이스에서는 항상 양방향 연관관계를 지원한다. 조인된 테이블을 조회할 때를 생각해보자면.. Member는 자신이 FK로 teamId를 사용해 Team을 조회할 수 있고, Team은 자신의 PK를 FK로 가진 Member들을 검색하는 방식으로 자신에 속한 Member들에 접근이 가능하다.
이러한 양방향 연관관계는 아래와 같이 표현할 수 있다.
@Entity
public class Team {
@Id @GeneratedValue
@Column(name = "TEAM_ID")
private Long id;
private String name;
@OneToMany(mappedBy = "team")
private List<Member> members = new ArrayList<>();
}
Member의 List를 참조변수로 둠으로써 양방향 연관관계를 나타냈다.
(이때 new ArrayList<>()로 굳이 초기화를 해준 이유는 관례 상 대부분 그렇게 하기 때문)
주의할 것은, 이번에는 Member가 아닌 Team 기준이기 때문에 @ManyToOne이 아니라 @OneToMany를 사용해야 한다는 것이다. 이때 속성으로 주어진 mappedBy에는 Member에서 자신을 참조하고 있는 참조변수의 이름을 넣어주는 것이다. (Team team)
사실 위와 같은 경우를 편의상 양방향 연관관계라고 말하기는 하지만 진정한 양방향 연관관계라고 볼 수는 없다.
단방향 연관관계 두개를 두어 양방향 연관관계처럼 사용하도록 한 것이다.
그런데 여기까지 왔다면 몇 가지 의문점이 생긴다.
1. 왜 Member에서는 @JoinColumn(name = "TEAM_ID")로 관계를 표현하고 Team에서는 @OneToMany(mappedBy = "team")관계를 표현하는가? (물론 Member에도 @ManyToOne이 있긴 하지만)
2. 두 테이블을 잇는 TEAM_ID라는 컬럼은 Member, Team 중 어느 쪽에서 관리해야 하는가?
위와 같은 문제는 양방향 연관관계에서 항상 발생하게 되는데 이것을 이해하기 위해 "연관관계의 주인(Owner)" 이라는 것을 정해야 한다. 양방향 관계를 완성하는 두 개의 단방향 관계 중 하나의 관계를 주인으로 지정하는 것이다.
일반적으로 FK를 가진 곳을 관계의 주인으로 잡는다. 즉, 1 : N 관계의 경우 N쪽으로 주인으로 하는 것이다.
(일반적으로라고 했지만 항상 이를 따르자)
그리고 이에 따라 아래와 같은 규칙들이 정해진다.
1. FK는 연관관계의 주인만이 관리한다.
2. 주인이 아닌 나머지 쪽은 FK에 대해 읽기만 수행할 수 있다.
3. 주인이 아닌 쪽에서 mappedBy 속성을 사용한다. (속성의 이름부터가 수동적인 느낌이라 주인에게는 어울리지 않는다. mappedBy = "관계의 주인")
