문제링크
https://school.programmers.co.kr/learn/courses/30/lessons/169199
문제 핵심
게임판 위의 장애물이나 게임판 가장자리까지 부딪힐 때까지 미끄러져 움직이는 것을 한 번의 이동으로 정의합니다.
다음은 보드게임판을 나타낸 예시입니다. ("."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.)
말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성해주세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.
알고리즘
-상하좌우로 d가 나오거나 끝에 닿을때까지 쭉가기
d가나오면 전칸이 g인지 확인하기
끝에 닿으면 해당칸이 g인지 확인하기
둘다 아니라면 횟수 1증가 하고 방문 처리하기
반복
코드
public static int solution(String[] board) {
int answer = 0;
String[][] map = new String[board.length][board[0].length()];
Integer[] start = new Integer[2];
Integer[] arrive = new Integer[2];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length(); j++) {
map[i][j] = String.valueOf(board[i].charAt(j));
if (map[i][j].equals("R")) {
start[0] = i;
start[1] = j;
} else if (map[i][j].equals("G")) {
arrive[0] = i;
arrive[1] = j;
}
}
}
Arrays.stream(map).forEach(row -> System.out.println(Arrays.toString(row)));
System.out.println("start:" + Arrays.toString(start) + " arrive:" + Arrays.toString(arrive));
answer = bfs(start, map, arrive);
System.out.println(answer);
return answer;
}
public static int bfs(Integer[] start, String[][] map, Integer[] arrvi) {
int count = -1;
int mw = map[0].length;
int mh = map.length;
boolean[][] visited = new boolean[map.length][map[0].length];
System.out.println("맵사이즈: " + mw + "," + mh);
Queue<Integer[]> queue = new LinkedList<>();
queue.offer(new Integer[] { start[0], start[1], 0 });
visited[start[0]][start[1]] = true;
printvisit(visited);
boolean arrive = false;
outer: while (!queue.isEmpty()) {
System.out.println("위치 탐색 예정 큐" +
queue.stream()
.map(Arrays::toString)
.toList());
Integer[] index = queue.poll();
Integer wid = index[1];
Integer hig = index[0];
System.out.println("현재좌표: " + hig + "," + wid + ",움직임: " + index[2]);
Integer right = wid + 1;
Integer left = wid - 1;
Integer up = hig - 1;
Integer down = hig + 1;
System.out.println("전진예정좌표: 오른쪽(" + hig + "," + right + ") 왼쪽(" + hig + "," + left + ") 위(" + up + "," + wid
+ ") 아래(" + down + "," + wid + ")");
if (right <= mw - 1) {
for (int i = right; i <= mw - 1; i++) {
System.out.println("오른쪽전진: " + hig + "," + i);
String flg = map[hig][i];
System.out.println("전진값: " + flg);
if (flg.equals("D")) {
System.out.println("D에 막힘");
if (map[hig][i - 1].equals("G")) {
System.out.println("D바로앞 arrvi에도착");
arrive = true;
count = index[2] + 1;
System.out.println("총움직임: " + count);
break outer;
} else if (!visited[hig][i - 1]) {
visited[hig][i - 1] = true;
queue.offer(new Integer[] { hig, i - 1, index[2] + 1 });
}
break;
} else if (!flg.equals("D")) {
if (i == mw - 1 && flg.equals("G")) {
System.out.println("끝에arrvi있으므로도착");
arrive = true;
count = index[2] + 1;
System.out.println("총움직임: " + count);
break outer;
} else if (i == mw - 1) {
System.out.println("끝에도착");
if (!visited[hig][i]) {
visited[hig][i] = true;
printvisit(visited);
queue.offer(new Integer[] { hig, i, index[2] + 1 });
}
break;
}
}
}
}
if (left >= 0) {
for (int i = left; i >= 0; i--) {
System.out.println("왼쪽전진: " + hig + "," + i);
String flg = map[hig][i];
System.out.println("전진값: " + flg);
if (flg.equals("D")) {
System.out.println("D에 막힘");
if (map[hig][i + 1].equals("G")) {
System.out.println("D바로앞 arrvi에도착");
arrive = true;
count = index[2] + 1;
System.out.println("총움직임: " + count);
break outer;
} else if (!visited[hig][i + 1]) {
visited[hig][i + 1] = true;
queue.offer(new Integer[] { hig, i + 1, index[2] + 1 });
}
break;
} else if (!flg.equals("D")) {
if (i == 0 && flg.equals("G")) {
System.out.println("끝에arrvi있으므로도착");
arrive = true;
count = index[2] + 1;
System.out.println("총움직임: " + count);
break outer;
} else if (i == 0) {
System.out.println("끝에도착");
if (!visited[hig][i]) {
visited[hig][i] = true;
printvisit(visited);
queue.offer(new Integer[] { hig, i, index[2] + 1 });
}
break;
}
}
}
}
if (up >= 0) {
for (int i = up; i >= 0; i--) {
System.out.println("위쪽전진: " + i + "," + wid);
String flg = map[i][wid];
System.out.println("전진값: " + flg);
if (flg.equals("D")) {
System.out.println("D에 막힘");
if (map[i + 1][wid].equals("G")) {
System.out.println("D바로앞 arrvi에도착");
arrive = true;
count = index[2] + 1;
System.out.println("총움직임: " + count);
break outer;
} else if (!visited[i + 1][wid]) {
visited[i + 1][wid] = true;
queue.offer(new Integer[] { i + 1, wid, index[2] + 1 });
}
break;
} else if (!flg.equals("D")) {
if (i == 0 && flg.equals("G")) {
System.out.println("끝에arrvi있으므로도착");
arrive = true;
count = index[2] + 1;
System.out.println("총움직임: " + count);
break outer;
} else if (i == 0) {
System.out.println("끝에도착");
if (!visited[i][wid]) {
visited[i][wid] = true;
printvisit(visited);
queue.offer(new Integer[] { i, wid, index[2] + 1 });
}
break;
}
}
}
}
if (down <= mh - 1) {
for (int i = down; i <= mh - 1; i++) {
System.out.println("아래쪽전진: " + i + "," + wid);
String flg = map[i][wid];
System.out.println("전진값: " + flg);
if (flg.equals("D")) {
System.out.println("D에 막힘");
if (map[i - 1][wid].equals("G")) {
System.out.println("D바로앞 arrvi에도착");
arrive = true;
count = index[2] + 1;
System.out.println("총움직임: " + count);
break outer;
} else if (!visited[i - 1][wid]) {
visited[i - 1][wid] = true;
queue.offer(new Integer[] { i - 1, wid, index[2] + 1 });
}
break;
} else if (!flg.equals("D")) {
if (i == mh - 1 && flg.equals("G")) {
System.out.println("끝에arrvi있으므로도착");
arrive = true;
count = index[2] + 1;
System.out.println("총움직임: " + count);
break outer;
} else if (i == mh - 1) {
System.out.println("끝에도착");
if (!visited[i][wid]) {
visited[i][wid] = true;
printvisit(visited);
queue.offer(new Integer[] { i, wid, index[2] + 1 });
}
break;
}
}
}
}
}
if (!arrive) {
return -1;
}
return count;
}
public static void printvisit(boolean[][] visited) {
System.out.println("visited 생성 시작");
for (int i = 0; i < visited.length; i++) {
for (int ii = 0; ii < visited[i].length; ii++) {
System.out.print(visited[i][ii] + " ");
}
System.out.println();
}
System.out.println("visited 생성 종료");
}
결과
gpt피드백
-딱히없다
배운점과느낀점
-새로운 bfs 문제였다
이전까지는 늘 한칸씩전진이였는데
이번에는 컬링같은 문제였다
다행이 금방 어떻게 풀어야 할지 감을 잡았다
'코테 > lvl2' 카테고리의 다른 글
| 프로그래머스 마법의 엘리베이터(lvl2) 풀어보기 (0) | 2026.09.26 |
|---|---|
| 프로그래머스 호텔 대실(lvl2) 풀어보기 (0) | 2026.09.17 |
| 프로그래머스 미로탈출(lvl2) 풀어보기 (0) | 2026.09.16 |
| 프로그래머스 거리두기 확인하기(lvl2) 풀어보기 (0) | 2026.09.15 |
| 프로그래머스 메뉴 리뉴얼(lvl2) 풀어보기 (0) | 2026.09.15 |