메뉴 닫기

[SWEA] 1953 [모의 SW 역량테스트] 탈주범 검거

SW Expert Academy 1953 탈주범 검거

계속해서 모의 SW역량 테스트 문제를 풀고 있다.
이번 문제도 BFS, DFS모두 가능하다.

접근방식

총 7가지의 파이프 방향을 어떻게 확인하고, 연결여부를 확인하는 로직이 문제의 핵심이다.
연결여부만 확인하고, 문제에서는 연결가능한 파이프의 갯수를 구하면 되기 때문에, 이부분은 BFS를 for문을 이용해 level별로 누적하다록 구현하였다.

나는 이 문제에서 비트마스킹을 적용하여 파이프 7개를 각각의 상:1 하:2 좌:4 우:8 이렇게 해서 구성하였다.
상하좌우 모두 연결된 아래 1번 파이프의 경우 1+2+4+8 이기 때문에 15로 마스킹 하였다.
또 연결여부를 확인하기 위해서는 출발점에서의 파이프 방향과 도착점에서의 파이프 방향이 대칭 되어야 하기 때문에 이를 메소드로 따로 빼서 계산해 주었다.

예를 들어서 4방향으로 연결된 1번 파이프에서 다음 2번 파이프를 탐색한후, 연결여부를 확인하기 위해서
1번 파이프가 오른쪽 방향으로 연결된 경우, 2번 파이프는 왼쪽으로 연결되어야 한다.

상,하,좌,우 모두 연결되어 있기 때문에 1+2+4+8 =15로 마스킹 하였다.

1번파이프는 4방향이기 때문에 상,하,좌,우로 다음 파이프에 접근을 시도한다.

좌,우가 연결되어있기 때문에 4+8 = 12로 마스킹 하였다.

해당 파이프가 1번파이프 우측에 있다고 가정할 때, 2번 파이프의 좌측이 열려(연결되어)있기 때문에 다음 Level에서 이동 가능하다.

코드

package com.algo.swea;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class SWEA1953Fugitive {
	static class Pos{
		int x,y,direction;

		public Pos(int x, int y, int direction) {
			super();
			this.x = x;
			this.y = y;
			this.direction =direction;
		}
	}

	private static int[] dx = {-1,1,0,0};
	private static int[] dy = { 0,0,-1,1};
	private static int N, M, R, C, L; 
	private static int[][] map;
	private static boolean[][] visited;
	private static LinkedList<Pos> q;
	private static int result;

	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("res/input_d9_1953.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		q = new LinkedList<>();
		int TC = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= TC; testCase++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			//입력의 크기 
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			//맨홀 뚜껑 좌표
			R = Integer.parseInt(st.nextToken()); 
			C = Integer.parseInt(st.nextToken());
			//이동 시간 L
			L = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			visited = new boolean[N][M];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < M; j++) {
					map[i][j] = toBit(Integer.parseInt(st.nextToken()));
				}
			}//input
			result = 1;
			bfs();
			sb.append("#").append(testCase).append(" ").append(result).append("\n");
		}
		System.out.print(sb);
		br.close();
	}

	private static void bfs() {
		q.clear();
		q.offer(new Pos(R,C, map[R][C]));
		visited[R][C]=true;
		int level =1;
		while(level<L &&!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				Pos p =q.poll();
				int nx = 0;
				int ny = 0;
				for (int d = 0; d <4 ; d++) {
					if((p.direction&(1<<d))!=0) {
						nx =p.x + dx[d];
						ny =p.y + dy[d];
						if(nx<0 || ny <0 || nx>=N || ny>=M) continue;
						if(visited[nx][ny] || map[nx][ny]==0) continue;
						if((map[nx][ny] & (1<<cDriection(d)))!=0){
							visited[nx][ny]=true;
							q.offer(new Pos(nx,ny, map[nx][ny]));
							result++;
						}
					}

				}
			}
			level++;
		}
	}
	//return counter direction 
	private static int cDriection(int d) {
		if(d == 0)
			return 1;
		else if(d==1)
			return 0;
		else if(d==2)
			return 3;
		else return 2;
	}
	private static int toBit(int direction) {
		switch (direction) {
			case 1 :
				return 15;// 1+2+4+8
			case 2 :
				return 3;//1+2;
			case 3 :
				return 12;//4+8;
			case 4 :
				return 9;//1+8;
			case 5 :
				return 10;//2+8;
			case 6 :
				return 6;//2+4;
			case 7 :
				return 5;//1+4; 
		}
		return 0;
	}

}

Related Posts

답글 남기기

이메일 주소는 공개되지 않습니다.

%d 블로거가 이것을 좋아합니다: