문제
링크 : https://www.acmicpc.net/problem/13460
해결 과정
빨간공과 파란공을 함께 다뤄줘야 할 것 같아서 static class 에 두 공의 좌표를 담고
어느 방향에서 왔는지 방향 정보까지 담았다.
처음에는 bfs로 풀다가 visit 체크를 누적으로 체크하고 해제하는 과정을 겪으면서
파라미터로 visit 을 넘기는 지경에 이르렀고 너무 비효율적인 것 같아서 dfs로 접근방식을 바꿨다.
입력은 가장자리 라인을 빼고 받았고, board 라는 이차원 int 배열을 만들었지만
보드를 업데이트 하는 과정은 빼도 될 것 같아서 뺐기에 board 배열은 사실상 무의미하다.
전반적인 공의 자리는 Marble 이 가지고 있고 visit으로 해당 칸으로 움직일 수 있는지 판단했기 때문이다.
가장 고민했던 부분은 불필요한 move를 하지 않도록 하는 아이디어였는데
이전에 움직인 방향으로 똑같이 움직일 필요가 없고, 나아가 이전에 움직인 방향과 반대 방향으로도 움직일 필요가 없어야 했다.
보드를 움직이면 끝까지 공이 이동하기에 같은 방향으로 또 움직여봤자 공의 변화는 없을 것이고,
왔던방향과 반대방향으로 움직인다면 이는 공이 왔다갔다를 한 것일 뿐이기 때문이다.
(예를들어, 아래로 보드를 움직였다면 다시 위로 움직일 필요가 없다는 것이다.)
그래서, dy dx 의 인덱스 0 1 2 3 을 각각 상,하,좌,우로 놓았기 때문에
다음 move를 할것인지 말것인지 판단할 때 이런 방식으로 했다.
for (int i = 0; i < 4; i++) {
boolean checkPrev = now.prevDir < 2;
boolean checkNext = i < 2;
if (checkPrev != checkNext || now.prevDir == -1) {<em>// 상~하 or 좌~우 -> 불필요</em>
<em>//다음 move 로직</em>
}
}이전의 방향과 다음 방향이 둘다 0 or 1 일 경우 상상 하하 상하 하상 중 하나일 것이고 (좌우의 경우도 마찬가지다)
이런 경우는 불필요한 move로 이어지기에 두 boolean 값이 서로 다를 때만 다음 move를 실행하도록 했다.
가장 까다로웠던 것은 dfs로 재귀 후 visit 체크를 풀어주는 과정이었는데
이 과정에서 위치가 변하지 않은 공이라면 그대로 두고, 변한 공이라면 기존의 visit으로 돌려주어야했는데
그냥 undoVisitCheck 이라는 메서드를 통해 이동하지 않은 공이라도 조건없이 체크를 풀어주도록 했었다.
static void undoVisitCheck(int prevY, int prevX, int nextY, int nextX) {
visit[prevY][prevX] = true;
visit[nextY][nextX] = false;
}결과적으로 undoVisitCheck 메서드의 4개의 파라미터 (prevY, prevX, nextY, nextX) 를 받을때
변하지 않았음에도 불구하고 메서드에 넣었기에 prev의 좌표와 next의 좌표가 같아져버려서
결과적으로는 그냥 변하지 않은 공의 좌표를 visit 체크를 해제해버리는 것이었고
이것 때문에 첫 제출때 96퍼에서 막혔었다.
디버깅을 몇번이나 한지 모르겠다. 질문게시판에 있는 테스트케이스도 죄다 넣어본것 같은데 거의 다 통과해서
어느부분이 잘못된지 찾느라고 너무 오래걸린 문제였다.
+추가로 큰 도움이 됐던 테스트케이스는 이거였다.
6 7
#######
##RB..#
#####.#
###O#.#
##….#
#######
답 : 8