Life Engineering
[SWEA 1953] 탈주범 검거 (Java) 본문
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution {
static int[] dr= {-1,1,0,0};
static int[] dc= {0,0,-1,1};
static int[][] directions= {{0},{0,1,2,3},{0,1}, {2,3}, {0,3}, {1,3}, {1,2}, {0,2}};
static int T, N, M;
static int R, C, L;
static int answer;
static int[][] map;
static boolean[][] visited;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=null;
T=Integer.parseInt(br.readLine());
for (int t=1; t<=T; t++) {
answer=0;
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=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]=Integer.parseInt(st.nextToken());
}
}
bfs(R, C);
System.out.println("#"+t+" "+answer);
}
}
private static void bfs(int startR, int startC) {
Queue<int[]> q=new LinkedList<>();
q.add(new int[] {startR, startC, map[startR][startC], 1});
visited[startR][startC]=true;
answer++;
while (!q.isEmpty()) {
int[] curr=q.poll();
int r=curr[0];
int c=curr[1];
int type=curr[2];
int time=curr[3];
if (time==L) {
break;
}
for (int d=0; d<directions[type].length; d++) {
int dir=directions[type][d];
int nr=r+dr[dir];
int nc=c+dc[dir];
if (nr<0 || nc<0 || nr>=N || nc>=M || map[nr][nc]==0) continue;
if (!visited[nr][nc] && isPossible(dir, map[nr][nc])) {
visited[nr][nc]=true;
q.add(new int[] {nr, nc, map[nr][nc], time+1});
answer++;
}
}
}
}
private static boolean isPossible(int dir, int num) {
int targetDir=-1;
if (dir==0) targetDir=1;
else if (dir==1) targetDir=0;
else if (dir==2) targetDir=3;
else targetDir=2;
for (int i=0; i<directions[num].length; i++) {
if (directions[num][i]==targetDir) return true;
}
return false;
}
}
처음엔 하드코딩으로 풀었다..
isPossible 부분이 마음에 안들었다..
좌측으로 이동한 것에는 우측을 향하는 파이프가 있어야 하고,
상측으로 이동한 것에는 하측을 향하는 파이프가 있어야 한다.. 라는 조건을 isPossible에다 구현했는데,
이럴 필요 없이 각 type당 방향성을 0,1 로 표시하면 된다. 그 후 상/좌/하/우 로 dr, dx를 배열해서 (d+2)%4 로 체크가 가능하도록 한다.. 고친 코드는 아래에 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution {
static int[] dr= {-1,0,1,0};
static int[] dc= {0,-1,0,1};
static int[][] directions= {{0,0,0,0},{1,1,1,1},{1,0,1,0}, {0,1,0,1}, {1,0,0,1},{0,0,1,1},{0,1,1,0},{1,1,0,0}};
static int T, N, M;
static int R, C, L;
static int answer;
static int[][] map;
static boolean[][] visited;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=null;
T=Integer.parseInt(br.readLine());
for (int t=1; t<=T; t++) {
answer=0;
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=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]=Integer.parseInt(st.nextToken());
}
}
bfs(R, C);
System.out.println("#"+t+" "+answer);
}
}
private static void bfs(int startR, int startC) {
Queue<int[]> q=new LinkedList<>();
q.add(new int[] {startR, startC, map[startR][startC], 1});
visited[startR][startC]=true;
answer++;
while (!q.isEmpty()) {
int[] curr=q.poll();
int r=curr[0];
int c=curr[1];
int type=curr[2];
int time=curr[3];
if (time==L) {
break;
}
for (int d=0; d<directions[type].length; d++) {
if (directions[type][d]==0) continue;
int nr=r+dr[d];
int nc=c+dc[d];
if (nr<0 || nc<0 || nr>=N || nc>=M || map[nr][nc]==0) continue;
if (!visited[nr][nc] && directions[map[nr][nc]][(d+2)%4]==1) {
visited[nr][nc]=true;
q.add(new int[] {nr, nc, map[nr][nc], time+1});
answer++;
}
}
}
}
}
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 가장 긴 팰린드롬 (Java) (0) | 2022.04.08 |
---|---|
[BOJ 17135] 캐슬 디펜스 (Java) (0) | 2022.04.08 |
[BOJ 1167] 트리의 지름 (Java) (0) | 2022.04.07 |
[프로그래머스] 숫자 게임 (Java) (0) | 2022.04.06 |
[BOJ 13459] 구슬 탈출 (Java) (0) | 2022.04.06 |