(JAVA) 1949. [모의 SW 역량테스트] 등산로 조성

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

이 문제도 마찬가지로, 어설픈 최적화는 시간만 잡아 먹음. 분명하게 설명할 수 있는 이유가 있을 때만 최적화를 하는게 살 길이다.
– 우선 맵 정보를 저장 (최대값이 담긴 vertex들은 따로 저장)
– 이 문제도 DFS로 완전 탐색을 수행.
– 각 최고점마다 총 4가지+4가지 경우를 탐색해야 함. (기본적인 좌우상하 4가지 + 기본 좌우상하 중 안 될 때 공사해서 갈 수 있는 경우 최대 4가지)
(공사 없이 좌 > 좌가 안 될 경우 공사해서 좌로 갈 수 있으면 공사 후 좌 /
공사 없이 우 > 우가 안 될 경우 공사해서 우로 갈 수 있으면 공사 후 우 /
공사 없이 상 > 상이 안 될 경우 공사해서 상으로 갈 수 있으면 공사 후 상 /
공사 없이 하 > 하가 안 될 경우 공사해서 하로 갈 수 있으면 공사 후 하)
– 위의 8가지 경우는 다음으로 진행할 때 경로 길이를 +1해서 진행
(단, 8가지 중 한 가지도 해당 안되는 경우 최종으로 보고 경로 길이 +1해서 global max length를 계산)
– 모든 경우를 탐색한 후, 최대 길이의 경로를 출력함

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

public class Solution {		
	public static int numN = 0;	// 맵 크기 (가로, 세로)
	public static int numK = 0;	// 공사 허용 한계 
	public static int maxLength = 0; // Global한 최대 길이

	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int i = 0; i < numCases; i++) {
				writer.write("#" + String.valueOf(i + 1) + " ");
				
				String[] tmp = reader.readLine().split(" ");
				numN = Integer.parseInt(tmp[0]);	// 맵 크기 (가로, 세로)
				numK = Integer.parseInt(tmp[1]);	// 공사 허용 한계 
				
				// 최대 높이 
				List<Vertex> maximumHeightList = new LinkedList<Vertex>();
				int maxHeight = 0;
				maxLength = 0;		// 적절한 초기화
				
				// map 작성
				int[][] mapArray = new int[numN][numN];
				for (int j = 0; j < numN; j++) { // 세로줄
					StringTokenizer tmp_ = new StringTokenizer(reader.readLine(), " ");
					int idx = 0; // 가로줄
					
					while (tmp_.hasMoreTokens()) {
						int tmp__ = Integer.parseInt(tmp_.nextToken());
						mapArray[idx][j] = tmp__;							
						
						// 최대값이 새로 나온 경우 기존 리스트 클리어
						if (tmp__ > maxHeight) {
							maxHeight = tmp__;
							maximumHeightList.clear();
						}

						// 새로운 최대값에 맞는 것만 삽입
						if (tmp__ == maxHeight)
							maximumHeightList.add(new Vertex(idx, j));
						
						idx++;
					}
				}
				
				for(Vertex v: maximumHeightList) {
					boolean[][] visited = new boolean[numN][numN];

					findPath(mapArray, visited, v.X, v.Y, 0, false);
				}
				
				writer.write(maxLength + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	// 실제 경로 탐색 
	// map: 지도, visited: 방문 정보, x: 현재 있는 곳 x 좌표, y: 현재 있는 곳 y 좌표, currentLength: 현재 길이, constructed: 공사 유무
	public static void findPath(int[][] map, boolean[][] visited, int x, int y, int currentLength, boolean constructed) {
		Vertex v = null;
		
		// 왼쪽
		v = findCandidate(map, visited, x, y, "L");
		if (v != null) {
			visited[x][y] = true;
			findPath(map, visited, v.X, v.Y, currentLength + 1, constructed);
			visited[x][y] = false; // 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
		}
		// 공사한 경우 포함 (단, 공사 없이도 이미 갈 수 있는 곳은 공사하지 않음. 오히려 length가 줄어들 수 있음) 
		if (v == null && constructed == false) {
			int[][] newMap = findConstructedMap(map, visited, x, y, "L", numK);
			if (newMap != null) {
				v = findCandidate(newMap, visited, x, y, "L");

				constructed = true;		// 공사가 된 경우에만 true로 
				visited[x][y] = true;	// 공사가 된 경우에만 true로 
				findPath(newMap, visited, v.X, v.Y, currentLength + 1, constructed);
				visited[x][y] = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
				constructed = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
			}
		}
		
		// 오른쪽
		v = findCandidate(map, visited, x, y, "R");
		if (v != null) {
			visited[x][y] = true;
			findPath(map, visited, v.X, v.Y, currentLength + 1, constructed);
			visited[x][y] = false; // 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
		}
		// 공사한 경우 포함 (단, 공사 없이도 이미 갈 수 있는 곳은 공사하지 않음. 오히려 length가 줄어들 수 있음) 
		if (v == null && constructed == false) {
			int[][] newMap = findConstructedMap(map, visited, x, y, "R", numK);
			if (newMap != null) {
				v = findCandidate(newMap, visited, x, y, "R");

				constructed = true;		// 공사가 된 경우에만 true로 
				visited[x][y] = true;	// 공사가 된 경우에만 true로 
				findPath(newMap, visited, v.X, v.Y, currentLength + 1, constructed);
				visited[x][y] = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
				constructed = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
			}
		}
		
		// 위
		v = findCandidate(map, visited, x, y, "U");
		if (v != null) {
			visited[x][y] = true;
			findPath(map, visited, v.X, v.Y, currentLength + 1, constructed);
			visited[x][y] = false; // 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
		}
		// 공사한 경우 포함 (단, 공사 없이도 이미 갈 수 있는 곳은 공사하지 않음. 오히려 length가 줄어들 수 있음) 
		if (v == null && constructed == false) {
			int[][] newMap = findConstructedMap(map, visited, x, y, "U", numK);
			if (newMap != null) {				
				v = findCandidate(newMap, visited, x, y, "U");

				constructed = true;		// 공사가 된 경우에만 true로 
				visited[x][y] = true;	// 공사가 된 경우에만 true로 
				findPath(newMap, visited, v.X, v.Y, currentLength + 1, constructed);
				visited[x][y] = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
				constructed = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
			}
		}
		
		// 아래
		v = findCandidate(map, visited, x, y, "D");
		if (v != null) {
			visited[x][y] = true;
			findPath(map, visited, v.X, v.Y, currentLength + 1, constructed);
			visited[x][y] = false; // 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
		}
		// 공사한 경우 포함 (단, 공사 없이도 이미 갈 수 있는 곳은 공사하지 않음. 오히려 length가 줄어들 수 있음) 
		if (v == null && constructed == false) {
			int[][] newMap = findConstructedMap(map, visited, x, y, "D", numK);
			if (newMap != null) {				
				v = findCandidate(newMap, visited, x, y, "D");
				
				constructed = true;		// 공사가 된 경우에만 true로 
				visited[x][y] = true;	// 공사가 된 경우에만 true로 
				findPath(newMap, visited, v.X, v.Y, currentLength + 1, constructed);
				visited[x][y] = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
				constructed = false;	// 다른 경우와 독립적이라는 것을 감안해서 처리가 끝나면 false로 
			}
		}
		
		// 더 이상 갈 곳이 없으면
		if (v == null) {
			// 그 전 vertex가 포함되었을 때 기준이므로, 이번 vertex가 마지막이면 그것도 포함해야 됨
			if (currentLength + 1 > maxLength)
				maxLength = currentLength + 1;
		}
	}
	
	// 주어진 방향으로 다음 후보를 탐색 
	public static Vertex findCandidate(int[][] map, boolean[][] visited, int x, int y, String direction) {
		int leftBound = 0;
		int rightBound = map[0].length - 1;
		int upBound = 0;
		int downBound = map.length - 1;
		
		// 왼쪽
		if (direction.equals("L") && x - 1 >= leftBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x - 1][y] != true && map[x][y] > map[x - 1][y])
				return new Vertex(x - 1, y);
		}
		
		// 오른쪽
		if (direction.equals("R") && x + 1 <= rightBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x + 1][y] != true && map[x][y] > map[x + 1][y])
				return new Vertex(x + 1, y);			
		}
		
		// 위
		if (direction.equals("U") && y - 1 >= upBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x][y - 1] != true && map[x][y] > map[x][y - 1])
				return new Vertex(x, y - 1);
		}
		
		// 아래
		if (direction.equals("D") && y + 1 <= downBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x][y + 1] != true && map[x][y] > map[x][y + 1])
				return new Vertex(x, y + 1);
		}

		return null;
	}
	
	// 주어진 방향으로 공사 가능한 경우 공사된 map 리턴, 불가능한 경우 null 리턴  
	public static int[][] findConstructedMap(int[][] map, boolean[][] visited, int x, int y, String direction, int numK) {
		int leftBound = 0;
		int rightBound = map[0].length - 1;
		int upBound = 0;
		int downBound = map.length - 1;
		
		int[][] map_ = new int[map[0].length][map.length];
		
		for (int i = 0; i < map_.length; i++) {
			for (int j = 0; j < map_[0].length; j++) {
				map_[j][i] = map[j][i];
			}
		}
				
		// 왼쪽
		if (direction.equals("L") && x - 1 >= leftBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x - 1][y] != true && map[x][y] > map[x - 1][y] - numK) {
				map_[x - 1][y] = map[x][y] - 1;
				return map_;
			}
		}
		
		// 오른쪽
		if (direction.equals("R") && x + 1 <= rightBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x + 1][y] != true && map[x][y] > map[x + 1][y] - numK){
				map_[x + 1][y] = map[x][y] - 1;
				return map_;
			}
		}
		
		// 위
		if (direction.equals("U") && y - 1 >= upBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x][y - 1] != true && map[x][y] > map[x][y - 1] - numK){
				map_[x][y - 1] = map[x][y] - 1;
				return map_;
			}
		}
		
		// 아래
		if (direction.equals("D") && y + 1 <= downBound) {
			// 아직 방문 안했고, 가려는 곳이 더 낮아야됨
			if (visited[x][y + 1] != true && map[x][y] > map[x][y + 1]  - numK){
				map_[x][y + 1] = map[x][y] - 1;
				return map_;
			}
		}

		return null;
	}
}

class Vertex {
	public int X;
	public int Y;
	
	public Vertex(int X_, int Y_) {
		this.X = X_;
		this.Y = Y_;
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.