문제 출처:
import java.util.Scanner;
public class swea_활주로건설 {
static int map[][];
static boolean visited[][];
static int res;
static int N, X;
static boolean isPossible;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
N = sc.nextInt();
X = sc.nextInt();
res = 0;
map = new int [N][N];
visited = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = sc.nextInt();
}
}
// 행 탐색
for (int i = 0; i < N; i++) {
isPossible = true;
for (int j = 1; j < N; j++) {
if(!isPossible) break;
int tmp = Math.abs(map[i][j] - map[i][j - 1]);
if(tmp > 1) {
isPossible = false;
break;
}else if(tmp == 1) {
if(map[i][j] > map[i][j - 1]) {
for (int k = j - 1; k > j - 1 - X; k--) {
if( k < 0 || visited[i][k] || map[i][j - 1] != map[i][k]) {
isPossible = false;
break;
}
visited[i][k] = true;
}
}else {
for (int k = j; k < j + X; k++) {
if(k >= N || visited[i][k] || map[i][j] != map[i][k]) {
isPossible = false;
break;
}
visited[i][k] = true;
}
}
}
}
if(isPossible)
res++;
}
// 열 탐색
visited = new boolean[N][N];
for (int j = 0; j < N; j++) {
isPossible = true;
for (int i = 1; i < N; i++) {
int tmp = Math.abs(map[i][j] - map[i - 1][j]);
if(tmp > 1) {
isPossible = false;
break;
}else if(tmp == 1) {
if(map[i][j] > map[i - 1][j]) {
for (int k = i - 1; k > i - 1 - X; k--) {
if(k < 0 || visited[k][j] || map[i - 1][j] != map[k][j]) {
isPossible = false;
break;
}
visited[k][j] = true;
}
}else {
for (int k = i; k < i + X; k++) {
if(k >= N || visited[k][j] || map[i][j] != map[k][j]) {
isPossible = false;
break;
}
visited[k][j] = true;
}
}
}
}
if(isPossible)
res++;
}
System.out.println("#" + tc + " " + res);
}
}
}
// 자세히 보면 열 탐색과 행 탐색은 열과 행만 바뀔 뿐 중복되는 코드이기 때문에 코드의 길이를 절반으로 줄일 수도 있다.
'알고리즘 문제 풀이' 카테고리의 다른 글
백준 2799 블라인드 (JAVA 자바) (0) | 2021.04.21 |
---|---|
백준 16235 나무 재테크(Java 자바) (0) | 2021.04.19 |
백준 2638 치즈 (Java 자바) (0) | 2021.04.04 |
백준 2407 조합 (JAVA 자바) (0) | 2021.04.01 |
백준 16953 A -> B (Java 자바) (0) | 2021.03.28 |