Article Image
Article Image
read
문제
입력
입력의 가장 첫 줄에는 총 테스트 케이스의 개수 T가 주어지며, 그 다음 줄부터 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫째 줄에는 N이 주어지고, 다음 N줄에 걸쳐서 핀볼 게임판의 모양이 주어진다.
게임판의 모양은 -1 이상 10 이하의 정수로 주어지며, 각 숫자는 한 칸씩 띄어져서 주어진다. 숫자에 따른 의미는 다음과 같다.
| -1 | 0 | 1~5 | 6~10 |
|---|---|---|---|
| 블랙홀 | 빈 공간 | 블록 | 웜홀 |
출력
테스트 케이스 t에 대한 결과는 “#t”를 찍고, 한 칸 띄고 정답을 출력한다.
(단, t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)
예제 입력 1
5
10
0 1 0 3 0 0 0 0 7 0
0 0 0 0 -1 0 5 0 0 0
0 4 0 0 0 3 0 0 2 2
1 0 0 0 1 0 0 3 0 0
0 0 3 0 0 0 0 0 6 0
3 0 0 0 2 0 0 1 0 0
0 0 0 0 0 1 0 0 4 0
0 5 0 4 1 0 7 0 0 5
0 0 0 0 0 1 0 0 0 0
2 0 6 0 0 4 0 0 0 4
6
1 1 1 1 1 1
1 1 -1 1 1 1
1 -1 0 -1 1 1
1 1 -1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
8
0 0 0 3 0 0 0 0
0 0 2 0 0 5 0 0
0 0 5 0 3 0 0 0
0 0 1 1 0 0 0 4
0 0 0 0 0 0 0 0
0 0 0 0 0 0 5 0
0 0 4 0 0 3 1 0
2 0 0 4 3 4 0 0
...
예제 출력 1
#1 9
#2 0
#3 7
#4 5
#5 19
풀이
이 문제는 구현 알고리즘 자체는 생각하기 쉽지만 시간초과를 어떻게 줄일지 깊게 생각해봐야 풀 수 있는 문제이다.
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.ArrayList;
class Solution
{
static int[][] map;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int N;
static int max;
static ArrayList<Pair>[] worm;
public static void main(String args[]) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int test_case = 1; test_case <= T; test_case++)
{
N = Integer.parseInt(br.readLine());
map = new int[N][N];
worm = new ArrayList[5];
for(int i=0; i<5; i++)
worm[i] = new ArrayList<>();
max = Integer.MIN_VALUE;
for(int i=0; i<N; i++) {
String[] input = br.readLine().split(" ");
for(int j=0; j<N; j++) {
map[i][j] = Integer.parseInt(input[j]);
if(map[i][j]>=6)
worm[map[i][j]-6].add(new Pair(i, j));
}
}
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(map[i][j]==0) {
map[i][j] = -1;
for(int k=0; k<4; k++)
bfs(i, j, k, 0);
map[i][j] = 0;
}
}
}
System.out.println("#"+test_case+" "+max);
}
}
public static void bfs(int x, int y, int d, int cnt) {
while(true) {
x = x+dx[d];
y = y+dy[d];
if(x<0 || x>=N || y<0 || y>=N) {
switch(d) {
case 0:
d=1; break;
case 1:
d=0; break;
case 2:
d=3; break;
case 3:
d=2; break;
default:
break;
}
cnt++;
}
else if(map[x][y]==-1) {
max = Math.max(max, cnt);
break;
}
else if(map[x][y]==0)
continue;
else if(map[x][y]==1) {
switch(d) {
case 0:
d=1; break;
case 1:
d=3; break;
case 2:
d=0; break;
case 3:
d=2; break;
default:
break;
}
cnt++;
}
else if(map[x][y]==2) {
switch(d) {
case 0:
d=3; break;
case 1:
d=0; break;
case 3:
d=2; break;
case 2:
d=1; break;
default:
break;
}
cnt++;
}
else if(map[x][y]==3) {
switch(d) {
case 0:
d=2; break;
case 1:
d=0; break;
case 2:
d=3; break;
case 3:
d=1; break;
default:
break;
}
cnt++;
}
else if(map[x][y]==4) {
switch(d) {
case 0:
d=1; break;
case 1:
d=2; break;
case 2:
d=3; break;
case 3:
d=0; break;
default:
break;
}
cnt++;
}
else if(map[x][y]==5) {
switch(d) {
case 0:
d=1; break;
case 1:
d=0; break;
case 2:
d=3; break;
case 3:
d=2; break;
default:
break;
}
cnt++;
}
else if(map[x][y]>=6) {
Pair one = worm[map[x][y]-6].get(0);
Pair two = worm[map[x][y]-6].get(1);
if(x==one.x && y==one.y) {
x = two.x;
y = two.y;
}
else {
x = one.x;
y = one.y;
}
}
}
}
public static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}