https://www.acmicpc.net/problem/14890
14890번: 경사로
첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.
www.acmicpc.net
풀이
길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는 경사로를 놓을 수 있는 조건을 만족해야 한다.
지나갈 수 있는 길의 개수를 구하기 위해서 먼저 행별로 탐색한 후 열별로 탐색한다.
열별로 탐색할 때는 원래 지도의 전치행렬을 만들어서 탐색한다.
private static int n, l;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
l = Integer.parseInt(st.nextToken());
int[][] 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());
}
}
int cnt = 0;
cnt += searchMap(map);
// 지도의 전치행렬 생성
int[][] transposeMap = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
transposeMap[i][j] = map[j][i];
}
}
cnt += searchMap(transposeMap);
System.out.println(cnt);
}
int searchMap(int[][] map)
지도를 행별로 탐색하여 지나갈 수 있는 길의 개수를 구한다.
각 행을 탐색할 때 경사로 설치 여부를 저장하는 boolean[] stairs를 생성하고, 경사로를 놓을 수 있는 경우 makeStairs() 메서드를 호출하여 경사로를 놓는다.
private static int searchMap(int[][] map) {
int cnt = 0;
for (int i = 0; i < n; i++) {
int first = map[i][0];
boolean flag = true;
boolean[] stairs = new boolean[n];
for (int j = 1; j < n; j++) {
if (first != map[i][j]) { // 경사로에 높이 차가 생기는 경우
if (first == map[i][j]+1) {
// 범위를 벗어나는 경우
if (j + l > n) {
flag = false;
break;
}
// L개의 연속된 칸의 높이가 모두 같아야 하며, 이미 계단이 놓여져 있지 않아야 경사로를 놓을 수 있다.
// 같지 않거나 계단이 이미 있으면 flag를 false로 변경 후, break
int[] copyMap = Arrays.copyOfRange(map[i], j, j+l);
boolean[] copyStairs = Arrays.copyOfRange(stairs, j, j+l);
if (Arrays.stream(copyMap).distinct().count() != 1 || isStair(copyStairs)) {
flag = false;
break;
}
// 경사로를 놓고, first와 j 값 업데이트
makeStairs(stairs, j, j+l);
first = map[i][j];
j = j+l-1;
}
else if (first + 1 == map[i][j]) {
// 범위를 벗어나는 경우
if (j - l < 0) {
flag = false;
break;
}
// L개의 연속된 칸의 높이가 모두 같아야 하며, 이미 계단이 놓여져 있지 않아야 경사로를 놓을 수 있다.
// 같지 않거나 계단이 이미 있으면 flag를 false로 변경 후, break
int[] copyMap = Arrays.copyOfRange(map[i], j-l, j);
boolean[] copyStairs = Arrays.copyOfRange(stairs, j-l, j);
if (Arrays.stream(copyMap).distinct().count() != 1 || isStair(copyStairs)) {
flag = false;
break;
}
// 경사로를 놓고, first 값 업데이트
makeStairs(stairs, j-l, j);
first = map[i][j];
}
else { // 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
flag = false;
break;
}
}
}
if (flag) { // 지나갈 수 있는 길인 경우
cnt++;
}
}
return cnt;
}
boolean isStair(boolean[] stairs)
주어진 stairs 배열에 경사로가 있으면 true를 리턴, 경사로가 없다면 false를 리턴한다.
void makeStairs(boolean[] stairs, int start, int end)
start부터 end-1까지 경사로를 설치한다. 즉, stairs[i]를 true로 변경한다.
private static boolean isStair(boolean[] stairs) {
for (int i = 0; i < stairs.length; i++) {
if (stairs[i]) {
return true;
}
}
return false;
}
private static void makeStairs(boolean[] stairs, int start, int end) {
for (int i = start; i < end; i++) {
stairs[i] = true;
}
}전체 코드
import java.io.*;
import java.util.*;
public class Main {
private static int n, l;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
l = Integer.parseInt(st.nextToken());
int[][] 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());
}
}
int cnt = 0;
cnt += searchMap(map);
// 지도의 전치행렬 생성
int[][] transposeMap = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
transposeMap[i][j] = map[j][i];
}
}
cnt += searchMap(transposeMap);
System.out.println(cnt);
}
private static int searchMap(int[][] map) {
int cnt = 0;
for (int i = 0; i < n; i++) {
int first = map[i][0];
boolean flag = true;
boolean[] stairs = new boolean[n];
for (int j = 1; j < n; j++) {
if (first != map[i][j]) { // 경사로에 높이 차가 생기는 경우
if (first == map[i][j]+1) {
// 범위를 벗어나는 경우
if (j + l > n) {
flag = false;
break;
}
// L개의 연속된 칸의 높이가 모두 같아야 하며, 이미 계단이 놓여져 있지 않아야 한다.
// 같지 않거나 계단이 이미 있으면 flag를 false로 변경 후, break
int[] copyMap = Arrays.copyOfRange(map[i], j, j+l);
boolean[] copyStairs = Arrays.copyOfRange(stairs, j, j+l);
if (Arrays.stream(copyMap).distinct().count() != 1 || isStair(copyStairs)) {
flag = false;
break;
}
// 계단을 세우고, first와 j 값 업데이트
makeStairs(stairs, j, j+l);
first = map[i][j];
j = j+l-1;
}
else if (first + 1 == map[i][j]) {
// 범위를 벗어나는 경우
if (j - l < 0) {
flag = false;
break;
}
// L개의 연속된 칸의 높이가 모두 같아야 하며, 이미 계단이 놓여져 있지 않아야 한다.
// 같지 않거나 계단이 이미 있으면 flag를 false로 변경 후, break
int[] copyMap = Arrays.copyOfRange(map[i], j-l, j);
boolean[] copyStairs = Arrays.copyOfRange(stairs, j-l, j);
if (Arrays.stream(copyMap).distinct().count() != 1 || isStair(copyStairs)) {
flag = false;
break;
}
// 계단을 세우고, first 값 업데이트
makeStairs(stairs, j-l, j);
first = map[i][j];
}
else { // 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
flag = false;
break;
}
}
}
if (flag) { // 계단을 놓는 경우
cnt++;
}
}
return cnt;
}
private static boolean isStair(boolean[] stairs) {
for (int i = 0; i < stairs.length; i++) {
if (stairs[i]) {
return true;
}
}
return false;
}
private static void makeStairs(boolean[] stairs, int start, int end) {
for (int i = start; i < end; i++) {
stairs[i] = true;
}
}
}
수정한 풀이
searchMap()을 호출하여 2차원 배열을 인자로 넘기는 대신, 2차원 배열의 한 행을 인자로 넘겨 각 행에 대해 탐색하도록 한다. 메서드 명도 searchMap()에서 searchOneLine()으로 변경했다.
import java.io.*;
import java.util.*;
public class Main {
private static int n, l;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
l = Integer.parseInt(st.nextToken());
int[][] 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());
}
}
// 지도의 전치행렬 생성
int[][] transposeMap = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
transposeMap[i][j] = map[j][i];
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
int[] copyMap = Arrays.copyOf(map[i], n);
if(searchOneLine(copyMap))
cnt++;
copyMap = Arrays.copyOf(transposeMap[i], n);
if(searchOneLine(copyMap))
cnt++;
}
System.out.println(cnt);
}
private static boolean searchOneLine(int[] map) {
boolean[] stairs = new boolean[n]; // 경사로 설치 여부
for (int j = 1; j < n; j++) {
int diff = map[j-1] - map[j];
if (diff > 1 || diff < -1) return false;
if (diff == 1) {
// 범위를 벗어나는 경우
if (j + l > n) {
return false;
}
// L개의 연속된 칸의 높이가 모두 같아야 하며, 이미 계단이 놓여져 있지 않아야 한다.
// 같지 않거나 계단이 이미 있으면 false를 리턴한다.
int[] copyMap = Arrays.copyOfRange(map, j, j+l);
boolean[] copyStairs = Arrays.copyOfRange(stairs, j, j+l);
if (Arrays.stream(copyMap).distinct().count() != 1 || isStair(copyStairs)) {
return false;
}
// 경사로를 놓고, j 값 업데이트
makeStairs(stairs, j, j+l);
j = j+l-1;
}
else if (diff == -1) {
// 범위를 벗어나는 경우
if (j - l < 0) {
return false;
}
// L개의 연속된 칸의 높이가 모두 같아야 하며, 이미 계단이 놓여져 있지 않아야 한다.
// 같지 않거나 계단이 이미 있으면 false를 리턴한다.
int[] copyMap = Arrays.copyOfRange(map, j-l, j);
boolean[] copyStairs = Arrays.copyOfRange(stairs, j-l, j);
if (Arrays.stream(copyMap).distinct().count() != 1 || isStair(copyStairs)) {
return false;
}
// 경사로 놓기
makeStairs(stairs, j-l, j);
}
}
return true;
}
private static boolean isStair(boolean[] stairs) {
for (int i = 0; i < stairs.length; i++) {
if (stairs[i]) {
return true;
}
}
return false;
}
private static void makeStairs(boolean[] stairs, int start, int end) {
for (int i = start; i < end; i++) {
stairs[i] = true;
}
}
}
Reference (다른 풀이)
- https://moonsbeen.tistory.com/282
- https://www.acmicpc.net/source/58193424
- https://yubh1017.tistory.com/55
728x90
'Algorithm 문제 풀이 > 백준' 카테고리의 다른 글
| [백준] 1325번 : 효율적인 해킹 - 자바[Java] (0) | 2023.06.23 |
|---|---|
| [백준] 20055번 : 컨베이어 벨트 위의 로봇 - 자바[Java] (0) | 2023.04.04 |
| [백준] 21608번 : 상어 초등학교 - 자바[Java] (0) | 2023.03.17 |
| [백준] 14719번 : 빗물 - 자바[Java] (0) | 2023.03.16 |
| [백준] 20164번 : 홀수 홀릭 호석 - 자바[Java] (0) | 2023.03.16 |
