알고리즘/백준
[DFS/백트래킹] 백준 18430번 무기공학 - JAVA
SHIN SANHA
2023. 11. 22. 03:03
반응형
오랜만에 강적 문제를 만났다...
1. 출처
18430번: 무기 공학
첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내
www.acmicpc.net
2. 설계
혼자서는 설계하기 어려웠던 문제이다. 그래서 유튜브의 힘을 좀 빌렸다. 감사합니다 코데풀님...
영상을 보니 어느정도 설계 가닥이 잡혔다.
1) (0,0)부터 부메랑의 중심지를 잡는다.
2) 부메랑을 만드려고 하는 위치 3곳이 visited되었는지 체크한다.
3) 4개 모양의 부메랑 중 가능한 부메랑을 찾는다. 단, 한 중심지에서 모든 부메랑의 경우를 볼 것이다.
static int[][] boomerangType1 = {{0,-1},{1,0}};
static int[][] boomerangType2 = {{-1,0},{0,-1}};
static int[][] boomerangType3 = {{-1,0},{0,1}};
static int[][] boomerangType4 = {{1,0},{0,1}};
그림 순서대로 TYPE 1~4이다.
4) 부메랑의 강도를 변수 value에 넣어주고, 다음 중심지로 dfs를 연속한다.
5) 부메랑의 모든 타입을 다 dfs로 돌았다면 row == N && col == M인 지점으로 한 번더 dfs로 들어간다.
boomerang(order+1, value);
6) row == N && col == M이 되었을 때 value에 계산된 부메랑의 총합과 현재 최고 강도라고 계산한 result 변수를 비교하여 result에 max값을 저장한다.
새로 알게 된 점
여기서 내가 새로 알게 된 점은 row와 col을 구하는 방법이다.
2중 for문을 돌려 행렬을 체크해주는 대신 order이라는 변수를 써서 열로 나누고 나머지를 구해주었다.
int row = order/M;
int col = order%M;
예를 들면 (1,1)인 지점은 order가 4인것이다. (0부터 시작해서...)
order = 0 -> 행 : order / M = 0/3 = 0 , 열 : order / M = 0%3 = 0
.
.
.
order = 4 -> 행 : order / M = 4/3 = 1 , 열 : order / M = 4%3 = 1
3. 전체 코드
import java.util.Scanner;
public class Main {
static int N;
static int M;
static int[][] map;
static boolean[][] visited;
static int[][] boomerangType1 = {{0,-1},{1,0}};
static int[][] boomerangType2 = {{-1,0},{0,-1}};
static int[][] boomerangType3 = {{-1,0},{0,1}};
static int[][] boomerangType4 = {{1,0},{0,1}};
static int result;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
map = new int[N][M];
visited = new boolean[N][M];
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
map[i][j] = sc.nextInt();
}
}
//입력 끝
boomerang(0, 0);
System.out.println(result);
}
public static void boomerang(int order, int value){//order은 0부터 시작
if(order == N*M){
result = Math.max(value, result);
return;
}
//2중 for문을 도는 것과 같다.
int row = order/M;
int col = order%M;
if(!visited[row][col]){
//부메랑 방향 정하기
if(inMap(new Direction(row+boomerangType1[0][0], col+boomerangType1[0][1]),new Direction(row+boomerangType1[1][0], col+boomerangType1[1][1]))){ //ㄱ
//visited 체크
visited[row][col] = true;
visited[row+boomerangType1[0][0]][col+boomerangType1[0][1]] = true;
visited[row+boomerangType1[1][0]][col+boomerangType1[1][1]] = true;
//다음 부메랑 만들러 가기
boomerang(order+1, value+map[row][col]*2 + map[row+boomerangType1[0][0]][col+boomerangType1[0][1]] + map[row+boomerangType1[1][0]][col+boomerangType1[1][1]]);
//visited 체크 해제
visited[row][col] = false;
visited[row+boomerangType1[0][0]][col+boomerangType1[0][1]] = false;
visited[row+boomerangType1[1][0]][col+boomerangType1[1][1]] = false;
}
if(inMap(new Direction(row+boomerangType2[0][0], col+boomerangType2[0][1]),new Direction(row+boomerangType2[1][0], col+boomerangType2[1][1]))){ //__ㅣ
//visited 체크
visited[row][col] = true;
visited[row+boomerangType2[0][0]][col+boomerangType2[0][1]] = true;
visited[row+boomerangType2[1][0]][col+boomerangType2[1][1]] = true;
//다음 부메랑 만들러 가기
boomerang(order+1, value + map[row][col]*2 + map[row+boomerangType2[0][0]][col+boomerangType2[0][1]] + map[row+boomerangType2[1][0]][col+boomerangType2[1][1]]);
//visited 체크 해제
visited[row][col] = false;
visited[row+boomerangType2[0][0]][col+boomerangType2[0][1]] = false;
visited[row+boomerangType2[1][0]][col+boomerangType2[1][1]] = false;
}
if(inMap(new Direction(row+boomerangType3[0][0], col+boomerangType3[0][1]),new Direction(row+boomerangType3[1][0], col+boomerangType3[1][1]))){ //ㄴ
//visited 체크
visited[row][col] = true;
visited[row+boomerangType3[0][0]][col+boomerangType3[0][1]] = true;
visited[row+boomerangType3[1][0]][col+boomerangType3[1][1]] = true;
//다음 부메랑 만들러 가기
boomerang(order+1, value + map[row][col]*2 + map[row+boomerangType3[0][0]][col+boomerangType3[0][1]] + map[row+boomerangType3[1][0]][col+boomerangType3[1][1]]);
//visited 체크 해제
visited[row][col] = false;
visited[row+boomerangType3[0][0]][col+boomerangType3[0][1]] = false;
visited[row+boomerangType3[1][0]][col+boomerangType3[1][1]] = false;
}
if(inMap(new Direction(row+boomerangType4[0][0], col+boomerangType4[0][1]),new Direction(row+boomerangType4[1][0], col+boomerangType4[1][1]))){ //|^^
//visited 체크
visited[row][col] = true;
visited[row+boomerangType4[0][0]][col+boomerangType4[0][1]] = true;
visited[row+boomerangType4[1][0]][col+boomerangType4[1][1]] = true;
//다음 부메랑 만들러 가기
boomerang(order+1, value + map[row][col]*2 + map[row+boomerangType4[0][0]][col+boomerangType4[0][1]] + map[row+boomerangType4[1][0]][col+boomerangType4[1][1]]);
//visited 체크 해제
visited[row][col] = false;
visited[row+boomerangType4[0][0]][col+boomerangType4[0][1]] = false;
visited[row+boomerangType4[1][0]][col+boomerangType4[1][1]] = false;
}
}
boomerang(order+1, value); //여기에 추가로 해주는 이유는 모든 부메랑 방향을 확인하고 나온 후 row==N && col==M 조건을 만족해야 return으로 max를 비교할 수 있기 때문이다.
}
public static boolean inMap(Direction d1, Direction d2){
if(d1.row<0 || d1.row>=N || d1.col<0 || d1.col>=M) return false;
if(visited[d1.row][d1.col]) return false;
if(d2.row<0 || d2.row>=N || d2.col<0 || d2.col>=M) return false;
if(visited[d2.row][d2.col]) return false;
return true;
}
public static class Direction{
int row;
int col;
public Direction(int row, int col){
this.row = row;
this.col = col;
}
}
}
내일은 싸피가자마자 아메리카노다 ㅠ
그래도 뿌듯!
반응형