[JAVA] SWEA 1953 탈주범 검거
문제
2차원 배열 위에서 주어진 파이프의 배치를 보고 주어진 시간 내에 탈주범이 방문할 수 있는 파이프의 위치의 개수를 찾는 문제이다.
입력
첫 줄에 총 테스트 케이스의 개수 T가 주어진다. 두 번째 줄부터 T개의 테스트 케이스가 차례대로 주어진다. 각 테스트 케이스의 첫 줄에는 지하 터널 지도의 세로 크기 N, 가로 크기 M, 맨홀 뚜껑이 위치한장소의 세로 위치 R, 가로 위치 C, 그리고 탈출 후 소요된 시간 L 이 주어진다.
그 다음 N 줄에는 지하 터널 지도 정보가 주어지는데, 각 줄마다 M 개의 숫자가 주어진다. 숫자 1 ~ 7은 해당 위치의 터널 구조물 타입을 의미하며 숫자 0 은 터널이 없는 장소를 의미한다.
출력
테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다. 각 줄은 “#x”로 시작하고 공백을 하나 둔 다음 정답을 기록한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 탈주범이 위치할 수 있는 장소의 개수이다.
풀이: bfs, 인접행렬
- 2차원 행렬에 Index값을 부여해서 1차원으로 치환한다. ( index = {세로 위치} X 행너비 + 가로위치 )
- 모든 위치에 대해 인접 리스트를 생성한다.
- 파이프의 배치를 보고 인접 리스트에 이동 가능한 위치의 인덱스를 추가한다.
- bfs로 방문 가능한 위치를 찾는다.
코드
package swea;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class p1953탈주범검거 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int testcase = Integer.parseInt(br.readLine());
for(int t=1; t<=testcase; t++) {
st = new StringTokenizer(br.readLine());
int height = Integer.parseInt(st.nextToken());
int width = Integer.parseInt(st.nextToken());
int posI = Integer.parseInt(st.nextToken());
int posJ = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(st.nextToken());
int grid[][] = new int[height][width];
for(int i=0; i<height; i++) {
st= new StringTokenizer(br.readLine());
for(int j=0; j<width; j++) {
grid[i][j] = Integer.parseInt(st.nextToken());
}
}
int num = height*width;
ArrayList<Integer>[] adj = new ArrayList[num];
for(int i=0; i<num; i++) {
adj[i] = new ArrayList<Integer>();
}
for(int i=0; i<height; i++) {
for(int j=0; j<width-1; j++) {
if((grid[i][j]==1||grid[i][j]==3||grid[i][j]==4||grid[i][j]==5)&&(grid[i][j+1]==1||grid[i][j+1]==3||grid[i][j+1]==6||grid[i][j+1]==7)) {
adj[i*width+j].add(i*width+j+1);
adj[i*width+j+1].add(i*width+j);
}
}
}
for(int i=0; i<height-1; i++) {
for(int j=0; j<width; j++) {
if((grid[i][j]==1||grid[i][j]==2||grid[i][j]==5||grid[i][j]==6)&&(grid[i+1][j]==1||grid[i+1][j]==2||grid[i+1][j]==4||grid[i+1][j]==7)) {
adj[i*width+j].add((i+1)*width+j);
adj[(i+1)*width+j].add(i*width+j);
}
}
}
int ans =0;
boolean visited[] = new boolean[num];
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(new int[] {width*posI+posJ, 0});
ans ++;
visited[width*posI+posJ] = true;
while(!queue.isEmpty()) {
int[] cur = queue.poll();
for(int next: adj[cur[0]]) {
if(!visited[next]&&cur[1]<time-1) {
visited[next] = true;
ans ++;
queue.offer(new int[] {next, cur[1]+1});
}
}
}
System.out.println("#"+t+" "+ans);
}
}
}
Author And Source
이 문제에 관하여([JAVA] SWEA 1953 탈주범 검거), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@taurus429/JAVA-SWEA-1953-탈주범-검거-y5gepe4y저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)