SWEA 1953 탈주범 검거 java 풀이
OnlineJudge

SWEA 1953 탈주범 검거 java 풀이

반응형

 

문제로이동

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com


 


문제 설명

얼핏 보면 간단한 BFS/DFS 문제로 보입니다.

하지만 주의해야 할 점이 있습니다.

 

 

자, 위와 같은 경우를 볼까요?

모든 방향(상하좌우)으로 나아갈 수 있는 1번 터널이지만 반대로 내가 가려고 하는 목적지에 도달이 불가능한 경우입니다.

위와 같이 좌,우로만 접근해야하는 터널이 있는 경우에 말이죠.

 

그래서 저는 다음과 같이 메소드를 구현했습니다.

 

첫째, 현재 터널 모양에서 나아갈 수 있는 방향을 반환(좌,우만 갈 수 있는 터널이라면 좌,우를 반환)하는 int[] getDirection 메소드

둘째, 다음 터널이 내가 지금 나아가려 하는 방향으로 접근이 가능한지 반환하는 Boolean checkDenied 메소드

 

이런 메소드들을 구현하고 마지막으로 로직을 정리하자면

 

  1. 현재 위치에서 어디로 나아갈 수 있는가?(getDirection)
  2. 다음 위치로 접근이 가능한가?(checkDenied)
  3. 접근이 가능하다면 이동하여 visited를 체크
  4. 1-3까지 L(이동시간)만큼 반복하다가 마지막에 정답 출력

 

위와 같이 구현되었습니다.


소스 코드

Java8

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

public class Solution_swea_1953_탈주범검거 {
	static StringBuilder sb = new StringBuilder();
	static int[][] field;
	static int[][] visited;
	static int N,M,L;
	static int direction[][] = new int[][] {{0,-1},{0,1},{-1,0},{1,0}};//상하좌우
	static Pos hole;
	static class Pos{
		int x,y;
		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = stoi(br.readLine());
		for(int t=1;t<=T;t++) {
			st = new StringTokenizer(br.readLine());
			N = stoi(st.nextToken());
			M = stoi(st.nextToken());
			int r = stoi(st.nextToken());
			int c = stoi(st.nextToken());
			hole = new Pos(c,r);
			L = stoi(st.nextToken());
			field = new int[N][M];
			visited = new int[N][M];
			for(int i =0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j =0;j<M;j++)field[i][j]=stoi(st.nextToken());
			}
			solution();
			int answer = 0;
			for(int i =0;i<N;i++)for(int j =0;j<M;j++)
				if(visited[i][j]>0)answer++;
			sb.append("#").append(t).append(" ").append(answer).append("\n");
		}	
		
	}
	static void solution() {
		Queue<Pos> q = new LinkedList<>();
		q.add(hole);
		visited[hole.y][hole.x]=1;
		while(!q.isEmpty()) {
			Pos cur = q.poll();
			if(visited[cur.y][cur.x]==L)continue;
			for(int d:getDirection(field[cur.y][cur.x])) {
				int nx = direction[d][0]+cur.x;
				int ny = direction[d][1]+cur.y;
				if(!canMove(nx,ny))continue;
				if(!checkDenied(d,field[ny][nx])||visited[ny][nx]>0||field[ny][nx]==0)continue;
				visited[ny][nx]=visited[cur.y][cur.x]+1;
				q.offer(new Pos(nx,ny));
			}
		}
	}
	static int[] getDirection(int arch) {//모양을 넘겨주면 나아갈 수 있는 방향을 반환함
		switch(arch) {
		case 1:return new int[] {0,1,2,3};
		case 2:return new int[] {0,1};
		case 3:return new int[] {2,3};
		case 4:return new int[] {0,3};
		case 5:return new int[] {1,3};
		case 6:return new int[] {1,2};
		case 7:return new int[] {0,2};
		}
		return new int[] {};
	}
	static boolean checkDenied(int d,int nextArch) {//현재 방향에서 다음 방향으로 접근 가능한지 반환함
		switch(nextArch) {
		case 1:return true;
		case 2:
			if(d==0||d==1)return true;
			return false;
		case 3:
			if(d==2||d==3)return true;
			return false;
		case 4:
			if(d==1||d==2)return true;
			return false;
		case 5:
			if(d==0||d==2)return true;
			return false;
		case 6:
			if(d==0||d==3)return true;
			return false;
		case 7:
			if(d==1||d==3)return true;
			return false;
		}
		return false;
	}
	static boolean canMove(int nx,int ny) {//좌표 범위 체크
		if(0>nx || 0>ny || nx>=M || ny>=N)return false;
		return true;
	}
	public static void main(String[] args) throws IOException {		
		input();
		System.out.println(sb);
	}
	static int stoi(String s) {
		return Integer.parseInt(s);
	}
}
반응형