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

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.