Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- java
- Arrays
- java 내림
- Math.ceil()
- Math.floor()
- 백준 18290
- Codility
- 백준 16935
- 알고리즘
- 백준 14391
- 코딩테스트
- time complexity
- 0으로 채우기
- 프로그래머스 숫자의 표현 java
- java 반올림
- 프로그래머스 연속된 수의 합 java
- 자바
- 백준 4375
- 백준 16927
- Algorithm
- 백준 11723
- mysql
- 프로그래머스 도둑질 java
- 백준 15661
- 프로그래머스 옹알이 java
- java 올림
- 프로그래머스 네트워크 java
- 백준 17425
- 네트워크
- sort
Archives
- Today
- Total
취미처럼
[백준] 18290번 NM과 K (1) 본문
https://www.acmicpc.net/problem/18290
18290번: NM과 K (1)
크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접
www.acmicpc.net
처음에 인접하지 않은 칸의 수의 합이라 하여 대각선을 더한 값이라고 생각하였으나
2칸 이상 떨어져도 인접하지 않은 칸이니 모두 탐색하여야 함
이미 탐색한 좌표를 다시 탐색하지 않기 위해 방문여부 체크
checkMove() 에서 인접한 좌표를 이미 방문하였다면 false리턴하여 다음 좌표로 넘어가게 함
import java.util.*;
import java.io.*;
public class Main {
public static int N, M, K, max;
public static int[][] arr;
public static boolean[][] visit;
public static int[] dy = {0, 1, 0, -1};
public static int[] dx = {1, 0, -1, 0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
arr = new int[N][M];
visit = new boolean[N][M];
max = Integer.MIN_VALUE;
for(int y = 0; y < N; y++) {
st = new StringTokenizer(br.readLine());
for(int x = 0; x < M; x++) {
arr[y][x] = Integer.parseInt(st.nextToken());
}
}
dfs(0, 0, 0, 0);
System.out.println(max);
}
public static void dfs(int y, int x, int depth, int sum) {
if(depth == K) {
max = Math.max(max, sum);
return;
}
for(int i = y; i < N; i++) {
for(int j = x; j < M; j++) {
if(!visit[i][j] && checkMove(i, j)) {
visit[i][j] = true;
dfs(y, x, depth + 1, sum + arr[i][j]);
visit[i][j] = false;
}
}
}
}
// 인접한 좌표인지 체크
public static boolean checkMove(int y, int x) {
boolean flag = true;
for(int i = 0; i < 4; i ++) {
int ny = y + dy[i];
int nx = x + dx[i];
if(ny >= 0 && ny < N && nx >= 0 && nx < M) {
if(visit[ny][nx]) {
flag = false;
}
}
}
return flag;
}
}
'Algorithm > 백준' 카테고리의 다른 글
[백준] 14501번 퇴사 (0) | 2021.03.03 |
---|---|
[백준] 1759번 암호 만들기 (0) | 2021.03.03 |
[백준] 15657번 N과 M (8) (0) | 2021.03.03 |
[백준] 15656번 N과 M (7) (0) | 2021.03.03 |
[백준] 15655번 N과 M (6) (0) | 2021.03.03 |
Comments