- 소요시간 : 1시간 30분
- 문제 사이트 : 백준
- 문제 수준 : 골드 2
- 문제 유형 : 구현, 시뮬레이션
- 다른 사람의 풀이를 참고 했는가 ? : O
-> 예제 입력 5를 통과하지 못해서 질문 게시판을 참고했다. - 문제 링크 : https://www.acmicpc.net/problem/17837
- 푼 날짜 : 2023.06.01
1. 사용한 자료구조 & 알고리즘
구현, 시뮬레이션, 큐, 스택을 사용했다.
2. 사고과정
1. 해당 좌표에 말이 쌓여있는 것을 어떻게 표현할 것인가?
👉 말이 쌓여있는것은 2차원 queue로 구현하려고 했었다. 하지만 우리는 1번째 말, 2번째 말이 해당 2차원 queue의 몇번째에 있는지 모르고, 찾기 위해서는 poll하고, 다시 add해야 한다. 이것이 구현하기 어려울 것이라고 판단. 그래서 2차원 ArrayList를 사용하기로 했다. 그러면 index로 접근이 가능했다.
💬 단점 : ArrayList를 사용하면, 나중에 말들을 없앨 때, 중간에 있는 좌표를 제거하면, 뒤에 있는 인덱스들이 하나씩 당겨진다. 하지만, 말이 그렇게 많이 쌓일 일이 없고, 또 전체 말의 개수가 10개 이하이다. 그러므로 이 문제에서는 ArrayList를 사용해도 될거라고 생각했다.
2. 다음 좌표가 빨간색일 때, 말들의 순서를 어떻게 바꿀 것인가?
👉 어떤 말들을 이동시킬 것인지 queue에 담아 두었다가, 이후 Stack에 옮겨 담는다. 이후 Stack에서 pop하면 그것이 말의 위치가 반전된 형태이다.
3. 말이 4개 이상 쌓인 것을 어떻게 확인할 것인가?
👉 말을 1번 옮길 때마다 checkMap이라는 메소드를 통해서 4개 이상 쌓인 말들이 있나 확인한다. 4개 이상 쌓인 곳이 있다면, count를 출력하면서 시스템을 종료한다. 여기서 나는, 말을 옮긴 후의 위치의 좌표만 확인해도 됐지만, 전체 맵의 좌표를 전부 확인했다. 맵의 크기가 작아서 상관 없을 것으로 생각했다.
4. 예제 입력 5를 통과 못했는데, 어떻게 해결했나?
👉 1시간 10분 째에 전체적인 코딩을 마치고, 예제 입력 5를 계속 통과 못했는데, 그 이유를 찾지 못해서 질문 게시판을 참고하기로 함. 예외는 이거였음.
✔️ 다음 좌표가 파란 좌표여서, 방향을 반전 시킨 형태로 한 칸 전진하는데, 그 좌표가 빨간 좌표라면, 빨간칸의 룰을 적용시켜야 한다.
이것을 읽고 띠용 ?? 했다. 이런 예외는 전혀 예상하지 못했다. 인지하고 난 후, 코딩해서 바로 정답을 맞췄다.
3. 풀이과정
- 1번 말부터 1칸씩 이동시키기 위해 해당 번호에 해당하는 말의 위치, (행, 열) 그리고 해당 위치의 몇번째 말인지 findHorse를 통해서 찾는다.
- 그리고 그 좌표부터, 그 위에 쌓인 말들은 해당 2차원 ArrayList에서 제거한 후, queue에 담는다.
- 다음 좌표가 빨간 좌표인지, 파란 좌표인지, 하얀 좌표인지에 따라서 다른 룰을 적용시킴.
- 말을 1번 이동시킬 때마다 4개 이상 쌓인 말이 있는지 확인.
4. 소스코드
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static ArrayList<Integer[]> list[][];
//오른쪽, 왼쪽, 위, 아래
static int dy[] = {0,0,-1,1};
static int dx[] = {1,-1,0,0};
static int map[][];
static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st=new StringTokenizer(br.readLine());
int N=Integer.parseInt(st.nextToken());
int K=Integer.parseInt(st.nextToken());
list=new ArrayList[N][N];
map=new int[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
list[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 row=Integer.parseInt(st.nextToken());
int col=Integer.parseInt(st.nextToken());
int dir=Integer.parseInt(st.nextToken());
list[row-1][col-1].add(new Integer[] {i+1,dir-1});
}
for(int i=0;i<1000;i++) {
count++;
moveHorse(K);
}
//1000번 째를 넘어가면 -1을 출력
System.out.println(-1);
}
//말을 옮기는 메소드
public static void moveHorse(int K) {
for(int i=1;i<=K;i++) {
//나를 포함해서, 위에 쌓인 말들을 담을 queue
Queue<Integer[]> queue=new LinkedList<>();
//해당 번호의 말을 찾는 메소드
int horse[] = findHorse(i);
//행, 열, 그 위치에서 몇번째 말인지
int row=horse[0];
int col=horse[1];
int idx=horse[2];
//나를 포함해서, 내 위에 쌓인 말들을 전부 queue에 add.
for(int j=idx;j<list[row][col].size();j++) {
queue.add(list[row][col].get(j));
}
//그 후, 나를 포함해서, 내위에 쌓인 말들은 전부 이전 위치에서 지운다.
while(list[row][col].size()!=idx)
list[row][col].remove(list[row][col].size()-1);
//어느 방향으로 갈지 정함. queue의 peek를 통해 알 수 있음.
int dir=queue.peek()[1];
//해당 방향으로 1칸 이동
int nextY=row+dy[dir];
int nextX=col+dx[dir];
//해당 좌표가 맵을 벗어났거나, 해당 좌표가 파란색이라면
if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length||map[nextY][nextX]==2) {
int switchedDir = -1;
//방향을 반전시킴.
switch(dir) {
case 0: switchedDir = 1; break;
case 1: switchedDir = 0; break;
case 2: switchedDir = 3; break;
case 3: switchedDir = 2; break;
}
//반전시켜서 1칸 전진
nextY = row+dy[switchedDir];
nextX = col+dx[switchedDir];
boolean mode=false;
boolean change=false;
//만약 1칸 전진시킨 좌표가 맵을 벗어나거나, 파란색이라면
if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length||map[nextY][nextX]==2) {
//처음의 원점 좌표가 됨.
nextY=row;
nextX=col;
}
//만약 1칸 이동시킨 좌표가 빨간색이라면 mode 는 true
else if(map[nextY][nextX]==1) {
mode=true;
}
//만약 1칸 이동시킨 좌표가 빨간색이라면
if(mode) {
//stack에 담아두었다가 pop하면서 말들의 쌓여있는 순서를 바꿈
Stack<Integer[]> stack=new Stack<>();
while(!queue.isEmpty()) {
Integer nowTemp[] = queue.poll();
//딱 1번만, 첫번째 말의 방향을 반전시킴
if(change==false) {
nowTemp[1]=switchedDir;
change=true;
}
stack.push(nowTemp);
}
//말들의 쌓여있는 순서를 바꾼대로 다음 좌표에 쌓음
while(!stack.isEmpty())
list[nextY][nextX].add(stack.pop());
//만약 다음 좌표가 하얀색이라면
}else {
//queue에서 poll하면서 다음 위치에 말들을 쌓음
while(!queue.isEmpty()) {
Integer nowTemp[] = queue.poll();
//딱 1번만, 첫번째 말의 방향을 반전시킴
if(change==false) {
nowTemp[1] = switchedDir;
change=true;
}
//말들의 원래 순서대로
list[nextY][nextX].add(nowTemp);
}
}
}
//만약 다음 좌표가 빨간색이라면
else if(map[nextY][nextX]==1) {
//stack에 담아두었다가 pop하면서 말들의 쌓여있는 순서를 바꿈
Stack<Integer[]> stack=new Stack<>();
while(!queue.isEmpty())
stack.push(queue.poll());
//말들의 쌓여있는 순서를 바꾼 대로 다음 좌표에 쌓음
while(!stack.isEmpty())
list[nextY][nextX].add(stack.pop());
}
//만약 다음 좌표가 하얀색이라면
else {
//그냥 다음 좌표에 순서대로 쌓음
while(!queue.isEmpty()) {
list[nextY][nextX].add(queue.poll());
}
}
//말들이 4개 이상 쌓여있는지 확인하는 메소드
checkMap();
}
}
//만약 4개 이상 말이 쌓인 곳이 있다면, count를 출력하고 시스템 종료
public static void checkMap() {
for(int i=0;i<map.length;i++) {
for(int j=0;j<map.length;j++) {
if(list[i][j].size()>=4) {
System.out.println(count);
System.exit(0);
}
}
}
}
//해당 번호의 말을 찾음
public static int[] findHorse(int num) {
for(int i=0;i<map.length;i++) {
for(int j=0;j<map.length;j++) {
for(int k=0;k<list[i][j].size();k++) {
Integer temp[]= list[i][j].get(k);
int horseNumber = temp[0];
//만약 해당 번호의 말의 번호가, 찾는 번호라면
//행, 열, 인덱스 반
if(horseNumber == num)
return new int[] {i,j,k};
}
}
}
//이것이 실행될 일은 없음. 하지만 없으면 에러가 나오기에 추가.
return new int[] {0,0,0};
}
}
5. 결과
6. 회고
생각하지 못한 예외가 1개 있다니 아쉽다.
이번 문제는 디버깅이 너무 어렵다고 생각해서 금방 질문게시판을 참고했는데
별로 좋은 태도는 아닌 것 같다.
다음 번에는 최소 30분 이상 혼자 찾아보자!
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212
