백준(14890번) - 경사로(Java) (구현)

 동서남북 4곳 모두에서 반대쪽으로 지나간다고 되어 있으니, 간단하게 (북 -> 남 / 서 -> 동) 이 2가지 경로만 반대쪽으로 넘어갈 수 있는지 검사해 봤다. 각각의 경우 안에서도 또 2가지 경우로 나눠지는데

 

북(서) -> 남(동)으로 움직이는 도중

 1. 앞칸이 지금 칸보다 한 칸 낮은 경우

 2. 앞칸이 지금 칸보다 한 칸 높은 경우

 

총 4가지 경우의 수를 고려해서 작성해 봤다.

import java.util.*;
import java.io.*;


public class Main
{
	static int n, l, ans;
	static int[][] map;
	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());
		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());
			}
		}
		
		for(int i = 0 ; i < n ; i++)
		{
			if(down(i)) ans++;
			
			if(right(i)) ans++;
		}
		
		System.out.println(ans);
	}
	public static boolean down(int c)
	{
		for(int i = 0 ; i < n ; i++)
		{
			if(i-1 >= 0 && map[i-1][c] - map[i][c] == 1)
			{
				int cnt = 1;
				
				for(int j = 1 ; j < l ; j++)
				{
					if(i+j >= n || map[i][c] != map[i+j][c]) return false;
					
					cnt++;
				}
				
				if(cnt < l) return false;
			}
			else if(i+1 < n && map[i+1][c] - map[i][c] == 1)
			{
				int cnt = 1;
				
				for(int j = 1 ; j < l ; j++)
				{
					if(i-j < 0 || map[i][c] != map[i-j][c]) return false;
					
					cnt++;
				}
				
				if(cnt < l) return false;
			}
		}
		
		return true;
	}
	public static boolean right(int r)
	{
		for(int i = 0 ; i < n ; i++)
		{
			if(i-1 >= 0 && map[r][i-1] - map[r][i] == 1)
			{
				int cnt = 1;
				
				for(int j = 1 ; j < l ; j++)
				{
					if(i+j >= n || map[r][i] != map[r][i+j]) return false;
					
					cnt++;
				}
				
				if(cnt < l) return false;
			}
			else if(i+1 < n && map[r][i+1] - map[r][i] == 1)
			{
				int cnt = 1;
				
				for(int j = 1 ; j < l ; j++)
				{
					if(i-j < 0 || map[r][i] != map[r][i-j]) return false;
					
					cnt++;
				}
				
				if(cnt < l) return false;
			}
		}
		
		return true;
	}
}

테스트 케이스조차 통과하지 못했는데 이런 코드로 작동할 경우 경사로를 놓은 칸에 중복으로 경사로를 넣지 말아야 한다는 문제 조건을 위반할 위험이 있기 때문이다. 이 부분을 보완하고 깔끔하게 다듬은 것이 정답 코드이다.

<문제>

https://www.acmicpc.net/problem/14890

14890번: 경사로

---

<소스코드>

import java.util.*;
import java.io.*;


public class Main
{
	static int n, l, ans;
	static int[][] map;
	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());
		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());
			}
		}
		
		for(int i = 0 ; i < n ; i++)
		{
			if(down(i)) ans++;
			
			if(right(i)) ans++;
		}
		
		System.out.println(ans);
	}
	public static boolean down(int c)
	{
		boolean[] visit = new boolean[n];    //경사로를 넣었는가를 의미
		
		for(int i = 0 ; i < n-1 ; i++)
		{
			if(Math.abs(map[i][c] - map[i+1][c]) > 1) return false;
			
			if(map[i+1][c] - map[i][c] == -1)	//밑이 1단 낮은 경우
			{
				for(int j = i+1 ; j <= i+l ; j++)
				{
					if(j >= n || map[i+1][c] != map[j][c] || visit[j]) return false;
					
					visit[j] = true;
				}
			}
			
			if(map[i+1][c] - map[i][c] == 1)	//밑이 1단 높은 경우
			{
				for(int j = i ; j > i-l ; j--)
				{
					if(j < 0 || map[i][c] != map[j][c] || visit[j]) return false;
					
					visit[j] = true;
				}
			}
		}
		
		return true;
	}
	public static boolean right(int r)
	{
		boolean[] visit = new boolean[n];    //경사로를 넣었는가를 의미
		
		for(int i = 0 ; i < n-1 ; i++)
		{
			if(Math.abs(map[r][i] - map[r][i+1]) > 1) return false;
			
			if(map[r][i+1] - map[r][i] == -1)	//밑이 1단 낮은 경우
			{
				for(int j = i+1 ; j <= i+l ; j++)
				{
					if(j >= n || map[r][i+1] != map[r][j] || visit[j]) return false;
					
					visit[j] = true;
				}
			}
			
			if(map[r][i+1] - map[r][i] == 1)	//밑이 1단 높은 경우
			{
				for(int j = i ; j > i-l ; j--)
				{
					if(j < 0 || map[r][i] != map[r][j] || visit[j]) return false;
					
					visit[j] = true;
				}
			}
		}
		
		return true;
	}
}