Problem
지도의 크기와 높이가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 문제입니다.
Solution
문제 특성상 코드가 굉장히 지저분하게 나올 수밖에 없다고 생각합니다.
우선 이 길이 맞는지 확인하는 canGo(x, y, d) 메소드를 만들었습니다.
시작 x, 시작 y, 그리고 가로 세로 여부를 판단하는 d 를 파라미터로 받습니다.
2차원으로 되어 있는 지도에서 길 하나만을 체크하는 것이기 때문에 height 라는 1차원 배열에 옮겨담았습니다.
그리고 visited 배열을 사용하였는데, 경사로를 중복으로 놓는 상황을 방지하기 위해서 만들었습니다.
height 배열을 1 ~ n-1 까지 돌면서 확인합니다.
- 높이가 같으면 패스
- 높이 차이가 2 이상이면
false - 내려가야 되는 경우
- 올라가야 되는 경우
이렇게 4가지 경우를 만들어서 예외처리를 하였습니다.
내려가야 하는 경우는 다음 인덱스부터 앞으로 길이 L 만큼
올라가야 하는 경우는 현재 인덱스부터 뒤로 길이 L 만큼
경사로를 놓을 땅이 있는지 확인합니다.
- 경사로 놓는 범위가 지도를 벗어나거나
j >= n - 경사로 놓는 땅의 높이가 다르거나
height[i+1] != height[j]orheight[i] != height[j] - 이미 다른 경사로가 놓여있는 경우
visited[j] == true
위 세가지 경우 중에 하나라도 만족하면 false 를 return 합니다.
만약 위에 세 조건에 걸리지 않고 무사히 for 문을 돌면 끝까지 도착했다는 뜻이므로 true 를 return 합니다.
x 가 0 이며 세로로 가는 길 또는 y 가 0 이며 가로로 가는 길 모두 확인하며 카운트를 해준 뒤에 출력해주면 됩니다.
Java Code
import java.io.*;
import java.util.*;
class Main {
static int stoi(String s) { return Integer.parseInt(s); }
static int n;
static int L;
static int[][] map;
static int count = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = stoi(st.nextToken());
L = stoi(st.nextToken());
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] = stoi(st.nextToken());
}
// 풀이 시작
for (int i=0; i<n; i++) {
if (canGo(i, 0, 0))
count++;
if (canGo(0, i, 1))
count++;
}
System.out.println(count);
}
// 한 줄이 경사로인지 확인 d = 0 이면 행검사, d = 1 이면 열검사
static boolean canGo(int x, int y, int d) {
int[] height = new int[n];
boolean[] visited = new boolean[n]; // 경사로가 이미 놓여있는지 체크
// 알아보기 쉽게 height 배열에 옮기기
for (int i=0; i<n; i++) {
height[i] = (d == 0) ? map[x][y+i] : map[x+i][y];
}
for (int i=0; i<n-1; i++) {
// 높이가 같으면 패스
if (height[i] == height[i+1]) {
continue;
}
if (Math.abs(height[i] - height[i+1]) > 1) {
return false;
}
// 내려가야되는 경우
if (height[i] - 1 == height[i+1]) {
for (int j=i+1; j<=i+L; j++) {
// j가 범위를 벗어나거나 높이가 다르거나 이미 경사로가 있는 경우
if (j >= n || height[i+1] != height[j] || visited[j] == true) {
return false;
}
visited[j] = true;
}
}
// 올라가야되는 경우
else if (height[i] + 1 == height[i+1]) {
for (int j=i; j>i-L; j--) {
if (j < 0 || height[i] != height[j] || visited[j] == true) {
return false;
}
visited[j] = true;
}
}
}
return true;
}
}Python Code
# -*- coding: utf-8 -*-
import sys
import itertools
N = L = 0
arr = []
def canGoPath(heights):
current = heights[0]
visited = [False for i in range(N)]
for i, height in enumerate(heights):
## 높이가 똑같으면 그냥 진행
if current == height:
continue
## 높은 곳으로 이동
## 지금까지 이동한 거리가 L보다 크거나 같으면 이동가능
elif current + 1 == height:
for j in range(i-1, i-1-L, -1):
if j < 0 or current != heights[j] or visited[j] == True:
return False
visited[j] = True
current = height
## 낮은 곳으로 이동
## 앞으로 이동할 곳에서 L만큼 같은 거리가 있으면 가능
elif current - 1 == height:
for j in range(i, i+L):
if j >= N or current - 1 != heights[j] or visited[j] == True:
return False
visited[j] = True
current = height
## 높이 차이가 1 이상이면 불가능
else:
return False
return True
def solve():
count = 0
for i in range(N):
if canGoPath(arr[i]):
count += 1
for j in range(N):
path = []
for i in range(N):
path.append(arr[i][j])
if canGoPath(path):
count += 1
print(count)
if __name__ == '__main__':
N, L = map(int, sys.stdin.readline().split())
for i in range(N):
arr.append(list(map(int, sys.stdin.readline().split())))
solve()'알고리즘 문제 > Samsung' 카테고리의 다른 글
| 백준 19238번. 스타트 택시 (Java) (0) | 2020.10.12 |
|---|---|
| 백준 14891번. 톱니바퀴 (Java, Python) (0) | 2019.01.01 |
| 백준 14889번. 스타트와 링크 (Java, Python) (0) | 2018.12.29 |
| 백준 14503번. 로봇 청소기 (Java, Python) (1) | 2018.12.29 |
| 백준 3190번. 뱀 (Java, Python) (1) | 2018.12.28 |
