(Java) 2112. [모의 SW 역량테스트] 보호 필름

Standard

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

왜 정답률이 낮은지 깨달은 문제.
– 뭔가 다른 방식의 완전 탐색으로 푸니까 시간 초과가 떠서 머리를 다시 굴림.
– 결국 각 막마다 A를 칠할 것이냐, B를 칠할 것이냐, 칠하지 않을 것이냐 해서 DFS로 모든 경우의 수를 탐색하는 문제였음.
– 각 막의 약품 처리 여부에 따라 지도가 계속 정보가 바뀌는데, 지도 전체를 계속 복사해서 쓰면 시간 소요가 크기 때문에, 수정하는 부분 (한 줄)만 백업해두고 값 바꾼 후 다시 값 복원하는 식으로 시간 효율을 올림.
– 어째저째 겨우겨우 통과함. 완전 탐색으로 짤 때, 쉽게 생각해야 가짓수를 쓸데없이 늘리는 실수를 안 함.

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

public class Solution {
	public static int minLevel = 1000;	// 최소값 찾는 것이기 때문에 최대 가능한 값보다 큰 값으로
	
	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) + " ");

				// 최소값 찾는 것이기 때문에 최대한 큰 값으로
				minLevel = 1000;

				// height: 두께 (Y), width: 가로크기 (X), threshold: 합격기준 
				String[] tmp = reader.readLine().split(" ");

				int height = Integer.parseInt(tmp[0]);
				int width = Integer.parseInt(tmp[1]);
				int threshold = Integer.parseInt(tmp[2]);

				// map 제작
				int[][] map = new int[height][width];
				for (int j = 0; j < height; j++) {
					String[] tmp_ = reader.readLine().split(" ");
					for (int k = 0; k < tmp_.length; k++) {
						map[j][k] = Integer.parseInt(tmp_[k]);
					}
				}
		
				// 한 번에 통과하는지 체크 
				if (checkPass(map, threshold) == true) {
					writer.write("0" + System.lineSeparator());
					continue;
				}
				// 안 되는 경우, 쭉 체크
				process(0, map, 0, threshold);

				writer.write(minLevel + System.lineSeparator());
				writer.flush();
			}			
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}	
	
	public static void process(int depth, int[][] map, int numTry, int threshold) {
		// 마지막 depth까지 안 되서 온 경우, 각 경우 처리 
		if (depth == map.length - 1) {
			// 안 고치고 가능한지 시도 (가장 적은 numTry 경우)
			if (checkPass(map, threshold) == true) {
				if (minLevel > numTry)
					minLevel = numTry;
				return;
			}
			
			// A 칠하고 나서 통과 여부 검사 
			// 지도 복구하기 위한 정보들 
			int[] toRestore = new int[map[depth].length];
			for(int i = 0; i < map[depth].length; i++)
				toRestore[i] = map[depth][i];
			Arrays.fill(map[depth], 0); // 0: A

			// A 칠해서 통과하면, 더 진행할 필요가 없음
			if (checkPass(map, threshold) == true) {
				if (minLevel > numTry + 1)
					minLevel = numTry + 1;
				
				// 갔다온 후 지도 복구
				for(int i = 0; i < map[depth].length; i++)
					map[depth][i] = toRestore[i];	

				return;
			}
			else {
				// 갔다온 후 지도 복구
				for(int i = 0; i < map[depth].length; i++)
					map[depth][i] = toRestore[i];	
			}
			
			// B 칠하고 나서 통과 여부 검사
			// 지도 복구하기 위한 정보들 
			toRestore = new int[map[depth].length];
			for(int i = 0; i < map[depth].length; i++)
				toRestore[i] = map[depth][i];
			Arrays.fill(map[depth], 1); // 1: B

			// B 칠해서 통과하면, 더 진행할 필요가 없음
			if (checkPass(map, threshold) == true) {
				if (minLevel > numTry + 1)
					minLevel = numTry + 1;
				
				// 갔다온 후 지도 복구
				for(int i = 0; i < map[depth].length; i++)
					map[depth][i] = toRestore[i];	
			}
			else {
				// 갔다온 후 지도 복구
				for(int i = 0; i < map[depth].length; i++)
					map[depth][i] = toRestore[i];	
			}
			
			return;	
		}
		
		// Case 1: A (A 칠하고 통과 여부 검사)
		int[] toRestore = new int[map[depth].length];
		for(int i = 0; i < map[depth].length; i++)
			toRestore[i] = map[depth][i];
		Arrays.fill(map[depth], 0);

		// A 칠해서 통과하면, 더 진행할 필요가 없음
		if (checkPass(map, threshold) == true) {
			if (minLevel > numTry + 1)
				minLevel = numTry + 1;
			
			// 갔다온 후 지도 복구
			for(int i = 0; i < map[depth].length; i++)
				map[depth][i] = toRestore[i];	

			return;
		}
		else {
			// A를 칠한 경우이므로 numTry 1 증가
			process(depth + 1, map, numTry + 1, threshold);			
		
			// 갔다온 후 지도 복구
			for(int i = 0; i < map[depth].length; i++)
				map[depth][i] = toRestore[i];
		}
		
		// Case 2: B (B 칠하고 통과 여부 검사)
		toRestore = new int[map[depth].length];
		for(int i = 0; i < map[depth].length; i++)
			toRestore[i] = map[depth][i];
		Arrays.fill(map[depth], 1);
		
		//B 칠해서 통과하면, 더 진행할 필요가 없음
		if (checkPass(map, threshold) == true) {
			if (minLevel > numTry + 1)
				minLevel = numTry + 1;

			// 갔다온 후 지도 복구
			for(int i = 0; i < map[depth].length; i++)
				map[depth][i] = toRestore[i];	
			
			return;
		}
		else {
			// B를 칠한 경우이므로 numTry 1 증가
			process(depth + 1, map, numTry + 1, threshold);	

			// 갔다온 후 지도 복구
			for(int i = 0; i < map[depth].length; i++)
				map[depth][i] = toRestore[i];	
		}

		// Case 3: X (약품 처리 안하고 통과 여부 검사)
		if (checkPass(map, threshold) == true) {
			if (minLevel > numTry)
				minLevel = numTry;
			return;
		}
		else {
			// 약품 처리 안 했으므로, numTry는 그대로
			process(depth + 1, map, numTry, threshold);
		}
	}
	
	public static boolean checkPass(int[][] map, int threshold) {
		boolean passed = true;
		
		// 시험 통과 여부 판별
		for (int i = 0; i < map[0].length; i++) {
			int currentIdx = map[0][i];
			int count = 1;

			for (int j = 1; j < map.length; j++) {
				if (currentIdx == map[j][i]) {
					count++;
					
					// 이미 합격한 경우 더 이상 진행하지 않음
					if (count == threshold)
						break;
				}
				else { // 달라진 경우 
					currentIdx = map[j][i];
					count = 1;
				}
			}
			
			// threshold를 넘긴 경우가 없을 경우, 실패로 처리하고 return
			if (count < threshold) {
				passed = false;
				break;
			}
		}
		
		return passed;
	}
}

(Java) 1953. [모의 SW 역량테스트] 탈주범 검거

Standard

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

어려운 문제는 아니지만, 그래도 고려할 사항들이 있는 문제들.
– 맵 형성 자체는 뭐 반복되는 거니까 설명 생략함.
– 다만 맵의 모든 곳에 파이프가 있는 것이 아니기 때문에, visited 체크 겸용으로 simpleMap 변수를 이용 (1은 파이프가 있음, 2는 방문한 곳)
– 기본적으로는 DFS로 depth를 하나씩 키워가면서 탐색하는 방식. 이미 탐색한 곳은 중복으로 후보에 넣지 않고 넓혀 나감.
– 함정 하나가, 현재 위치의 파이프 모양을 보고 방향을 결정지어도 갈 방향의 파이프가 맞지 않으면 갈 수 없는 방향임. 이를 감안해서 후보지 알고리즘을 작성함.
– 시간이 안 됐지만 더 이상 후보지가 없다면 미리 빠져나와서 시간 절약.

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

public class Solution {		
	public static int[][] map = null;
	public static int[][] simpleMap = null;
	
	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(" ");
				int height = Integer.parseInt(tmp[0]);		// 세로 크기 (Y)
				int width = Integer.parseInt(tmp[1]);		// 가로 크기 (X)
				int manholeX = Integer.parseInt(tmp[3]);	// 맨홀 X
				int manholeY = Integer.parseInt(tmp[2]);	// 맨홀 Y
				int timeCons = Integer.parseInt(tmp[4]);	// 소요한 시간

				// Map 만들기
				map = new int[width][height];
				// simpleMap은 visited 겸용으로 쓰임 (1: 파이프가 있음, 2: 방문함)
				simpleMap = new int[width][height]; 
				
				for (int j = 0; j < height; j++) {
					int idx = 0;

					StringTokenizer st = new StringTokenizer(reader.readLine(), " ");
					while (st.hasMoreTokens()) {
						int tmp_ = Integer.parseInt(st.nextToken());
						if (tmp_ != 0) {
							map[idx][j] = tmp_;
							simpleMap[idx][j] = 1;
						}
						
						idx++;
					}
				}
				
				int maxApproach = 0;
				// 가야할 후보지 
				Queue<Vertex> myQueue = new LinkedList<Vertex>();
				// 이미 간 곳 stack에 넣음 (사실 count로 해도 됨)
				Stack<Vertex> myStack = new Stack<Vertex>();
				
				// 맨홀에서 시작
				myQueue.add(new Vertex(manholeX, manholeY));
				
				// 갈 수 있는 후보를 모두 탐색
				for (int j = 1; j <= timeCons; j++) {
					// 1000, 1000은 탈출 조건을 위함 (일종의 구분자 역할)
					myQueue.add(new Vertex(1000, 1000));
					
					Vertex v = myQueue.poll();
					while ((v.X == 1000 && v.Y == 1000) == false) {
						// 현재 vertex: v
						if (simpleMap[v.X][v.Y] == 1) { // 중복 방문 허용 안함
							simpleMap[v.X][v.Y] = 2;
							myStack.add(v);
							
							List<Vertex> cand = findCandidate(v.X, v.Y);
							// 아직 방문하지 않은 다음 공간이 있는 경우
							if (cand != null) {
								// 해당 후보 vertex 추가
								for (Vertex vv: cand) {
									myQueue.add(vv);
								}
							}
						}
						
						v = myQueue.poll();
					}
					
					// 더 이상 갈 수 있는 공간이 없으면 탈출
					if (myQueue.size() == 0)
						break;
				}
				
				maxApproach = myStack.size();
				writer.write(maxApproach + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public static List<Vertex> findCandidate(int x, int y) {
		List<Vertex> cand = new LinkedList<Vertex>();
		
		boolean toLeft = false;
		boolean toRight = false;
		boolean toUp = false;
		boolean toDown = false;
		
		// 현재 위치가 어디로 갈 수 있는지 확인 (왼쪽)
		switch (map[x][y]) {
		case 1: case 3: case 6: case 7:
			int leftBound = 0;
			// 왼쪽에 공간이 있고, 파이프가 있고 방문하지 않은 곳
			if (x - 1 >= leftBound && simpleMap[x - 1][y] == 1)
				toLeft = true;
		}
		
		// 현재 위치가 어디로 갈 수 있는지 확인 (오른쪽)
		switch (map[x][y]) {
		case 1: case 3: case 4: case 5:
			int rightBound = map.length - 1;
			// 오른쪽에 공간이 있고, 파이프가 있고 방문하지 않은 곳
			if (x + 1 <= rightBound && simpleMap[x + 1][y] == 1)
				toRight = true;
		}

		// 현재 위치가 어디로 갈 수 있는지 확인 (위)
		switch (map[x][y]) {
		case 1: case 2: case 4: case 7:
			int upBound = 0;
			// 위에 공간이 있고, 파이프가 있고 방문하지 않은 곳
			if (y - 1 >= upBound && simpleMap[x][y - 1] == 1)
				toUp = true;
		}

		// 현재 위치가 어디로 갈 수 있는지 확인 (아래)
		switch (map[x][y]) {
		case 1: case 2: case 5: case 6:
			int downBound = map[x].length - 1;
			// 아래에 공간이 있고, 파이프가 있고 방문하지 않은 곳
			if (y + 1 <= downBound && simpleMap[x][y + 1] == 1)
				toDown = true;
		}

		if (toLeft == true) {
			switch (map[x - 1][y]) {
			// 왼쪽에 있는 파이프가 오른쪽을 향한 경우에만 접근 가능
			case 1: case 3: case 4: case 5:
				cand.add(new Vertex(x - 1, y));
			}
		}
		if (toRight == true) {
			switch (map[x + 1][y]) {
			// 오른쪽에 있는 파이프가 왼쪽을 향한 경우에만 접근 가능
			case 1: case 3: case 6: case 7:
				cand.add(new Vertex(x + 1, y));
			}
		}
		if (toUp == true) {
			switch (map[x][y - 1]) {
			// 위에 있는 파이프가 아래를 향한 경우에만 접근 가능
			case 1: case 2: case 5: case 6:
				cand.add(new Vertex(x, y - 1));
			}
		}
		if (toDown == true) {
			switch (map[x][y + 1]) {
			// 아래에 있는 파이프가 위를 향한 경우에만 접근 가능
			case 1: case 2: case 4: case 7:
				cand.add(new Vertex(x, y + 1));
			}
		}
		
		return cand;
	}
}

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

(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_;
	}
}

(Java) 1767. [SW Test 샘플문제] 프로세서 연결하기

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf&categoryId=AV4suNtaXFEDFAUf&categoryType=CODE

괜히 뭔가 최적화한다고 로직을 복잡하게 짜는거 보다, 완전 탐색으로 깔끔하게 짜는게 더 나았던 케이스.
– 우선 맵 정보를 저장
– 이미 edge에 있는 CPU들은 전선 길이 0으로 연결되어 있다고 가정하고 있으므로, 계산에서 제외
– 나머지 edge에 있지 않은 CPU들은 추가하는 경우 (좌/우/상/하)와 추가하지 않는 경우까지 5가지 경우가 있음 (즉 O(5n)의 복잡도)
– Edge에 있지 않은 CPU들을 대상으로, DFS로 recursive하게 (즉 재귀적으로) brute-force search (완전 탐색)을 수행함
(매 단계 추가하는 경우는 갱신된 정보를, 추가하지 않는 경우 갱신되지 않은 정보를 다음 단계로 넘김)
– 매 단계 CPU가 추가될 수 없는 경우라도, 추가하지 않는 경우로 간주하고 계속 다음 단계로 넘어가기 때문에, 최종적인 update는 마지막 단계에서 수행
– 마지막 단계에서 상하좌우로 추가하는 경우와  추가하지 않는 경우까지 감안해서 CPU 수가 최대로 되면서 전선 길이가 최소로 되는 경우를 계속 global하게 업데이트함

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

public class Solution {	
	public static int maxCPU = 0;		// Global한 최대 CPU 값 
	public static int minValue = 1000;	// Global한 최소 전선 길이
	public static ArrayList<Vertex> myList = null;	// 처리해야 될 CPU 목록 (파라미터로 넘기기 번거로워서)
	
	public static void main(String[] args) throws IOException {
		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) + " ");
				
				int numN = Integer.parseInt(reader.readLine());	// 맵 가로/세로 폭
			
				maxCPU = 0;			// 매번 초기화 
				minValue = 1000;	// 매번 초기화
				myList = new ArrayList<Vertex>(); // 매번 초기화
				
				// map 작성
				int[][] mapArray = new int[numN][numN];
				for (int j = 0; j < numN; j++) {	// j가 세로라는 것을 유의해야 함
					StringTokenizer tmp = new StringTokenizer(reader.readLine(), " ");
					int idx = 0;
					while (tmp.hasMoreTokens()) {
						int tmp_ = Integer.parseInt(tmp.nextToken());
						if (tmp_ != 0) {
							mapArray[idx][j] = tmp_;
							
							// edge에 있는 요소들은 따로 계산할 필요가 없음 (j-세로 나 idx-가로가 edge에 걸쳐져 있으면 추가하지 않음)
							if (!(j == 0 || j == numN - 1 || idx == 0 || idx == numN - 1))
								myList.add(new Vertex(idx, j));
						}
						
						idx++;
					}
				}

				// 실제로 CPU를 최대한 넣으면서, 길이가 최소인 경우를 탐색 
				// depth=0, currentNumCPU=0, currentLength=0
				search(0, mapArray, 0, 0);

				writer.write(minValue + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	// 실제로 CPU를 최대한 넣으면서, 길이가 최소인 경우를 탐색 
	// (currentDepth: 몇 번째 vertex를 처리해야 하는가, map: 현재까지의 지도 처리 정보, currentNumCPU: 현재까지 포함된 CPU의 수, currentLength: 현재까지의 전선 길이)
	public static void search(int currentDepth, int[][] map, int currentNumCPU, int currentLength) {
		// 현재 처리해야 될 CPU 정보 획득
		Vertex v = myList.get(currentDepth);

		// 만약 최대 깊이까지 왔다면 
		if (currentDepth == myList.size() - 1) {
			int maxCPU_ = 0;		// Local한 최대 CPU 갯수
			int minValue_ = 1000;	// Local한 최소 전선 길이 
			
			int retVal = 0;
			// 위로 전선을 연결할 수 있는 경우
			if ((retVal = safeToAdd(map, v.X, v.Y, "U")) > 0) {
				maxCPU_ = currentNumCPU + 1;
				// 필요한 경우 최소값 갱신
				if (minValue_ > currentLength + retVal)
					minValue_ = currentLength + retVal;
			}
			// 아래로 전선을 연결할 수 있는 경우
			if ((retVal = safeToAdd(map, v.X, v.Y, "D")) > 0) {
				maxCPU_ = currentNumCPU + 1;
				// 필요한 경우 최소값 갱신
				if (minValue_ > currentLength + retVal)
					minValue_ = currentLength + retVal;
			}
			// 왼쪽으로 전선을 연결할 수 있는 경우
			if ((retVal = safeToAdd(map, v.X, v.Y, "L")) > 0) {
				maxCPU_ = currentNumCPU + 1;
				// 필요한 경우 최소값 갱신
				if (minValue_ > currentLength + retVal)
					minValue_ = currentLength + retVal;
			}
			// 오른쪽으로 전선을 연결할 수 있는 경우
			if ((retVal = safeToAdd(map, v.X, v.Y, "R")) > 0) {
				maxCPU_ = currentNumCPU + 1;
				// 필요한 경우 최소값 갱신
				if (minValue_ > currentLength + retVal)
					minValue_ = currentLength + retVal;
			}
			// 전선이 연결될 수 없는 경우 (minValue_가 계속 1000)
			if (minValue_ == 1000) {
				maxCPU_ = currentNumCPU;	// 이전 정보 그대로
				minValue_ = currentLength; 	// 이전 정보 그대로
			}
			
			// Global값보다 더 큰 경우 갱신 
			if (maxCPU_ > maxCPU) {
				maxCPU = maxCPU_;
				minValue = minValue_;
			}
			// Global 값과 같지만 전선 길이가 더 짧은 경우 갱신 
			else if (maxCPU_ == maxCPU) {
				if (minValue > minValue_)
					minValue = minValue_;
			}
			
			return;
		}

		// 이외의 기본 경우 
		int retVal = 0;
		// 위로 갈 수 있는 경우. 위로 전선 연결한 정보 (Map, CPU 갯수, 전선 길이) 갱신 후 다음 단계로 넘어감 
		if ((retVal = safeToAdd(map, v.X, v.Y, "U")) > 0)
			search(currentDepth + 1, addToMap(map, v.X, v.Y, "U"), currentNumCPU + 1, currentLength + retVal);
		// 아래로 갈 수 있는 경우. 아래로 전선 연결한 정보 (Map, CPU 갯수, 전선 길이) 갱신 후 다음 단계로 넘어감 
		if ((retVal = safeToAdd(map, v.X, v.Y, "D")) > 0)
			search(currentDepth + 1, addToMap(map, v.X, v.Y, "D"), currentNumCPU + 1, currentLength + retVal);
		// 왼쪽으로 갈 수 있는 경우. 왼쪽으로 전선 연결한 정보 (Map, CPU 갯수, 전선 길이) 갱신 후 다음 단계로 넘어감 
		if ((retVal = safeToAdd(map, v.X, v.Y, "L")) > 0)
			search(currentDepth + 1, addToMap(map, v.X, v.Y, "L"), currentNumCPU + 1, currentLength + retVal);
		// 오른쪽으로 갈 수 있는 경우. 오른쪽으로 전선 연결한 정보 (Map, CPU 갯수, 전선 길이) 갱신 후 다음 단계로 넘어감 
		if ((retVal = safeToAdd(map, v.X, v.Y, "R")) > 0)
			search(currentDepth + 1, addToMap(map, v.X, v.Y, "R"), currentNumCPU + 1, currentLength + retVal);
		// 현재 CPU를 추가 안하는 경우. 정보 갱신 없이 다음 단계로 넘어감 
		search(currentDepth + 1, map, currentNumCPU, currentLength);
	}
	
	// 추가 가능한 경우 추가된 전선 길이를 (>0), 불가능한 경우 -1을 리턴함
	// (map: 현재 지도, x: 추가할 CPU의 x 좌표, y: 추가할 CPU의 y 좌표, direction: 전선의 방향)
	public static int safeToAdd(int[][] map, int x, int y, String direction) {
		int isSafe = 0;
		
		switch (direction) {
		// 위로 추가하는 경우 
		case "U":
			for (int i = y - 1; i >= 0; i--) {
				if (map[x][i] != 0) {
					isSafe = -1;
					break;
				}
				else
					isSafe++;
			}
			break;
		// 아래로 추가하는 경우 
		case "D":
			int tmp_ = map[x].length;
			for (int i = y + 1; i < tmp_; i++) {
				if (map[x][i] != 0) {
					isSafe = -1;
					break;
				}
				else
					isSafe++;
			}
			break;
		// 왼쪽으로 추가하는 경우 
		case "L":
			for (int i = x - 1; i >= 0; i--) {
				if (map[i][y] != 0) {
					isSafe = -1;
					break;
				}
				else
					isSafe++;
			}
			break;
		// 오른쪽으로 추가하는 경우 
		case "R":
			int tmp2_ = map.length;
			for (int i = x + 1; i < tmp2_; i++) {
				if (map[i][y] != 0) {
					isSafe = -1;
					break;
				}
				else
					isSafe++;
			}
			break;
		}
		
		return isSafe;
	}
	// 실제 지도에 추가 (addToMap 자체는 검증 기능이 없으므로 safeToAdd 함수로 확인 먼저 할 필요 있음)
	// (map: 현재 지도, x: 추가할 CPU의 x 좌표, y: 추가할 CPU의 y 좌표, direction: 전선의 방향)
	// (리턴값: 갱신된 지도)
	public static int[][] addToMap(int[][] map, int x, int y, String direction) {
		// 2차원 배열 복사
		int[][] map_ = new int[map.length][map.length];
		
		for(int i=0; i<map.length; i++)
			for(int j=0; j<map[i].length; j++)
				map_[i][j]=map[i][j];
		
		// CPU 있는 곳은 1로 마킹되어 있음. 전선은 2로 마킹함
		switch (direction) {
		case "L": // 2
			for (int i = x - 1; i >= 0; i--) {
				map_[i][y] = 2;
			}
			break;
		case "R": // 2
			int tmp2_ = map.length;
			for (int i = x + 1; i < tmp2_; i++) {
				map_[i][y] = 2;
			}
			break;
		case "U": // 2
			for (int i = y - 1; i >= 0; i--) {
				map_[x][i] = 2;
			}
			break;
		case "D": // 2
			int tmp_ = map[x].length;
			for (int i = y + 1; i < tmp_; i++) {
				map_[x][i] = 2;
			}
			break;
		}
		
		return map_;
	}
}

// CPU 정보 (x, y 좌표)
class Vertex {
	public int X;
	public int Y;
	
	public Vertex(int X_, int Y_) {
		this.X = X_;
		this.Y = Y_;
	}
}

Java library for Linux Server Socket (incl. C Server Example)

Standard

(Source link: https://github.com/prl85/LinuxClientSocket-for-Java)

Java library (client socket) for communicating with Linux server socket

Requirement
– Java client: any OS
– C server: Linux OS

BLE iBeacon Scanner for Android 5.0 and later (optimized for Android 7)

Standard

(Source link: https://github.com/prl85/BLEScanner/)

iBeacon Scanner for Android 5.0 and later – resolves ‘5 tries per 30 seconds’ limit by Android 7.0 (Nougat) and later
https://stackoverflow.com/questions/43114913/android-7-0-ble-scan-no-result
https://blog.classycode.com/undocumented-android-7-ble-behavior-changes-d1a9bd87d983
https://github.com/AltBeacon/android-beacon-library/issues/418

To resolve the scan block problem by Android 7.0, my library (BLEScanner) did made some trick like following;

  • Regardless of the requested period for scanning, BLEScanner performs BLE scan at least 6 seconds (30/5= 6 s)
  • BLEScanner externally returns scan result of requested period like the scanning is performed during the period, but internally it continues to scan without reporting result
  • If new scan is requested before BLE scan is terminated internally, BLEScanner returns scan results of new request period, and delays real BLE scan stop if necessary.

By separating result report period and real BLE scan stop timing, users can be perceived that the scan is performed during request period, while BLEScanner internally adjusts real BLE scan stop timing to cope with ‘5 tries per 30 seconds’ limit.