구슬 탈출2

전혀 생각하지 못한 부분(틀린 이유) 구멍의 위치 = Map[i][j].equals("0")인데 구멍의 위치 입력 정보가 제대로 저장되지 않았다!!!

최단거리 찾는 BFS 탐색 문제였다.

기울기를 상하좌우 4가지 방향으로 기울여서 빨간색 구슬을 구멍 위치에 이동시키는 게임이다. 파란색 구슬이 구멍 위치에 도달하면 구슬 이동을 종료한다.

기울기를 4가지 방향으로 움직인다 : 결국 4가지 방향으로 이동시킨다는 것은 생각할 수 있었다. 하지만 처음에는 공간차원의 이해가 필요한가 싶었다.

이 문제는 결국, 상하좌우 4가지 방향으로 구슬을 이동시켜서 구멍위치로 도달시키는, BFS 문제였다.

편의상 빨간 구슬R, 파란 구슬B, 구멍H라고 하자. R, B 둘다 기울이는 방향대로 이동을 시켰지만 R을 중심으로 코드를 구현했다. => 파란 구슬이 구멍에 도달하면 바로 종료되는 것이기 때문에, 파란 구슬이 이동하는 것을 먼저 구현한다!?

이 문제의 대박적 포인트⭐️

일단 큐를 이용해 반복적으로 BFS를 구현하지 않은 것도 원인이지만, 이동한 후 R과 B의 위치가 동일하다면 바로 종료시켜버렸는데 이 부분이 틀렸다.

다른 사람들의 풀이법을 보면, 이동한 후 R과 B의 위치가 동일할 경우, 이동한 방향 4가지에 대해 이동하기 전의 R, B의 R(x1,y1) , B(x2,y2) 의 대소 비교에 따라 위치가 동일하더라도 위치를 조작(?)해서 선후관계를 설정할 수 있다!!!!!!

문제 정리

  1. BFS 문제, BFS 이동횟수 = 기울인 횟수⭐️

  2. 빨간 구슬, 파란 구슬 동시에 이동하기 때문에 위치나 각 위치 방문체크할 때 동시에 해주는 것이 편한 듯하다. => 클래스 정의할 때 2개 구슬 위치 함께 저장, 방문체크 시에 2개 구슬 위치 함께 방문 체크하기 위해 4차원 배열로 구현

  3. 빨간, 파란 구슬 이동한 후 위치가 동일하다면 바로 실패& 게임 종료하는 것이 아니라 4가지 이동방향에 따라 이동하기 전의 구슬(x,y)좌표 대소 비교를 통해 2개 구슬 선후 관계 설정 가능!

3번째 풀었을 때 틀린 이유

  1. 2개 구슬이 동일한 위치에 도달했을 경우 현재 구슬들의 위치 기준으로 이동하기 전과 후의 x,y 좌표를 비교해야하는데 클래스의 멤버변수와 동일한 바람에(?) cur.Rx,cur.Ry,cur.Bx,cur.By가 아니라 처음에 입력받을 때의 초기위치 Rx,Ry,Bx,By로 비교해버려서 틀렸다! => 입력 저장할 때, 변수를 따로 저장하는 방법은 지양하거나 => 클래스의 멤버변수와 중복되는 변수이름을 지양하거나 nRx = nBx, nRy = nBy이긴하지만, 위치값을 조정해야할 때, nRx,nRy를 기준으로 +-1을 한다고 할 때, nBx = nRy + 1을 해도 되지만, nBx = nBx +1 이렇게 본인의 값에 +-1 처리를 하는 것이 더 괜찮을 것 같다. (변수가 많이 나와버리면 헷갈리기 쉬운듯.)

  2. 10번 이하로 움직인 경우만 정답처리가 된다. 현재 이동횟수인 cnt를 0번부터 시작한다면 cnt가 9가 됐을 때 10번 움직인 것이므로, 큐에서 뽑은 노드의 cnt가 10이상이 되면 무효한 값이므로 -1을 리턴하면 된다!(재귀함수를 생각해보라!) 이에 따라, 빨간 구슬이 구멍에 도달했을 때, cnt가 10이하인지 부가적으로 조건 체크하지 않아도 된다. 이미 큐에서 꺼낼 때부터 10번 이하 움직임에 대한 조건처리를 해주었기 때문이다!

이해하지 못했는데 이해한 부분 다음 이동 좌표 값이 #가 아닐 때까지 반복한다. 로직을 정확하게, 명확하게 정의하기. 이동시키기 전에, 이동하려는 좌표가 #인지 먼저 검서하고 나서 이동해야한다.

  1. 기존 코드 : 현재 위치에서 dir 방향으로 이동 시키고 난 후, nx,ny 위치가 #가 아닌 경우에 이동 처리. 따라서 먼저 이동시켜버리기 때문에 현재 테두리 위치인 0행으로 이동하고, 이미 0행(#인칸)에 위치해있음에도 불구하고, while문을 통과해버려서 다시 상/하/좌/우 중 상 방향으로 한번더 이동하기 때문에 -1 배열인덱스 초과에러가 발생하는 것이다.

    for(int dir=0;dir<4;dir++) {
				//1.구슬 이동
				//1-1.파란구슬
				int nBx = cur.Bx+dx[dir];
				int nBy = cur.By+dy[dir];
				//#만나기전까지 계속 이동
				while(!Board[nBx][nBy].equals("#")) {
					nBx += dx[dir];
					nBy += dy[dir];
					if(Board[nBx][nBy].equals("O")) {//이동중 구멍만나면 이동 반복 종료
						break;
					}
				}

  2. 정답 : 현재위치에서 dir 방향으로 이동시킨 값이 #가 아닌 경우에 이동 처리.

    for(int dir=0;dir<4;dir++) {
				//1.구슬 이동
				//1-1.파란구슬
				int nBx = cur.Bx;
				int nBy = cur.By;
				//#만나기전까지 계속 이동
				while(!Board[nBx+dx[dir]][nBy+dy[dir]].equals("#")) {
					nBx += dx[dir];
					nBy += dy[dir];
					if(Board[nBx][nBy].equals("O")) {//이동중 구멍만나면 이동 반복 종료
						break;
					}
				}

  3. 차이점 : 1번의 경우, 이미 이동시키고 난 후에 조건 판단을 하는 것은 순서가 잘못됐다. 2번처럼, 이동시키고 난 후의 값이 #가 아닌 경우에만 처리를 해야한다.

Previous상어중학교Next구슬 탈출

Last updated