17837 새로운 게임2 : https://www.acmicpc.net/problem/17837
Problem
Solve
문제 구현의 접근은 오래걸리지 않았지만 디버깅에 너무 많은 시간이 낭비된 문제. 몇시간동안 잡지 못한 이슈가 3차원 배열로 체스 말이 겹쳐져있는 여부를 확인하는 식으로 구현했어서 겹쳐져있는 체스 말을 함께 이동시킬때 이동시키는 체스 말 위에 있는 말들의 뒷처리를 완벽하게 하지 못한걸 캐치못해서 테스트케이스 3번에서 자꾸 이상한 값을 반환하는것이였다.
이 이슈는 2차원 배열에다 list로 변경해서 함께 이동할 체스 말들을 하나씩 지워가는 식으로 구현해서 해결했다.
체스판의 상태를 저장한 int[][] map과 체스판 위의 말들의 위치와 겹쳐져있는 말을 저장하는 List[][] unitMap, 주어진 말들의 정보를 저장하는 Unit[] units을 사용했다.
map,unitMap,units초기화와 방향 전환을 위해 주어지는 체스 말을0 : 위, 1 : 왼쪽, 2: 아래, 3 : 오른쪽으로 갱신- turn이 1000이 초과할때까지 체스 말 이동 함수 반복
- 체스 말 이동 함수가 false를 반환하면 4개 이상의 말이 겹쳐진 것으로 해당 turn값 반환
- 체스 말 이동 함수
- units을 순환
- 이동할 체스 판이
파란색 || 벽인지흰색 || 빨간색인지 확인 파란색 || 벽이라면 현재 방향과 반대 방향으로 움직일 좌표 생성- 그 좌표가
파란색 || 벽이라면 체스 말의 방향만 바꿔준다. - 그 좌표가
흰색 || 빨간색이라면 체스 말의 방향을 바꿔주고2번으로 돌아간다.
- 그 좌표가
흰색 || 빨간색이라면 현재 체스 말과 겹쳐져있는 체스 말들을 list에 저장한다.- boolean을 통해 현재 좌표에 저장되어있는 체스 말 중 이동시킬 체스 말을 찾을때까지 반복한다.
- 체스 말을 찾게 되면 boolean을
true로 변경시켜 다음 저장된 체스 말 부터 함께 이동시키기 위해 list에 저장한다.
- 흰색이라면 list에 저장된 체스 말을 순서대로 다음 좌표에 저장한다.
- 빨간색이라면 list에 저장된 체스 말을 반대로 다음 좌표에 저장한다.
- 다음 좌표에 저장되어있는 체스 말의 개수가 4개 이상이라면
false를 반환하여 함수 종료 - 4개가 아니라면 다음 체스 말 이동
Code
public class 새로운게임2 {
static int N;
static int K;
static int[][] map;
static List<Unit>[][] unitMap;
static Unit[] units;
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, -1, 0, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new int[N][N];
unitMap = new ArrayList[N][N];
units = new Unit[K];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
unitMap[i][j] = new ArrayList<>();
}
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine(), " ");
int y = Integer.parseInt(st.nextToken()) - 1;
int x = Integer.parseInt(st.nextToken()) - 1;
int d = Integer.parseInt(st.nextToken());
//이동 방향 변환
if (d == 1) {
d = 3;
} else if (d == 2) {
d = 1;
} else if (d == 3) {
d = 0;
} else {
d = 2;
}
units[i] = new Unit(y, x, i, d);
unitMap[y][x].add(units[i]);
}
int turn = 0;
int result = -1;
//turn이 1000을 초과하거나 move에서 false를 반환할때까지 반복
while (turn++ <= 1000) {
if(!move(turn)){
result = turn;
break;
}
}
bw.write(String.valueOf(result));
bw.flush();
bw.close();
}
//체스 말 이동
static boolean move(int turn) {
//주어진 체스 말 순환
for (int i = 0; i < K; i++) {
Unit current = units[i];
int y = current.y;
int x = current.x;
int ny = current.y+dy[current.direction];
int nx = current.x+dx[current.direction];
//파란색 || 벽
if(ny<0 || nx<0 || ny>=N || nx>=N || map[ny][nx] == 2){
//반대 방향
int reverseDirection = (current.direction+2)%4;
int reverseY = y+dy[reverseDirection];
int reverseX = x+dx[reverseDirection];
current.direction = reverseDirection;
//반대로 이동할 좌표가 파란색 || 벽이 아니라면 현재 체스 말의 방향만 바뀐 상태로 다시 탐색
if(reverseY>=0 && reverseX>=0 && reverseY<N && reverseX<N && map[reverseY][reverseX]!=2){
i--;
continue;
}
}
//빨간색 || 흰색
else{
List<Unit> group = new ArrayList<>();
boolean flag = false;
//현재 말 위치에 있는 말들
for(int j=0;j<unitMap[y][x].size();j++){
Unit unit = unitMap[y][x].get(j);
//이동 시킬 말을 좌표에서 찾았다면 그 다음 말과 함께 list에 저장
if(unit.num == current.num){
flag = true;
unit.y = ny;
unit.x = nx;
group.add(unit);
//이동시킬 체스 말은 현재 좌표에서 제거
unitMap[y][x].remove(unit);
j--;
continue;
}
//이동 시킬 체스 말 위에 올라가 있는 체스 말들 list에 저장
if(flag){
unit.y = ny;
unit.x = nx;
group.add(unit);
unitMap[y][x].remove(unit);
j--;
}
}
//이동할 좌표가 흰색이라면 list에 저장된 순서대로 다음 좌표에 추가
if(map[ny][nx]==0){
for(int k=0;k<group.size();k++){
unitMap[ny][nx].add(group.get(k));
}
}
//이동할 좌표가 빨간색이라면 list에 저장된 역순으로 다음 좌표에 추가
else if(map[ny][nx]==1){
for(int k=group.size()-1;k>=0;k--){
unitMap[ny][nx].add(group.get(k));
}
}
//다음 좌표에 최종으로 저장된 체스 말의 개수가 4개 이상이라면 함수 종료
if(unitMap[ny][nx].size()>=4){
return false;
}
}
}
return true;
}
static class Unit {
int y;
int x;
int num;
int direction;
public Unit(int y, int x, int num, int direction) {
this.y = y;
this.x = x;
this.num = num;
this.direction = direction;
}
}
}
Result
Reference
내 꿈은 좋은 개발자