문제링크
https://school.programmers.co.kr/learn/courses/30/lessons/154540
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제 핵심
지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다
각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.
알고리즘
-모든섬 모음 배열만들기
섬이없다면 -1리턴
섬마다 bfs 활용해 이어진데까지돌아보기
돌아보면서 식량합과 방문한 섬담기
방문한섬은 다시 돌아보지않기
코드
public static int[] solution(String[] maps) {
int[] answer = {};
String[][] map = new String[maps.length][maps[0].length()];
List<Integer[]> starts = new LinkedList<>();
int landc=0;
for (int i = 0; i < maps.length; i++) {
for (int j = 0; j < maps[i].length(); j++) {
map[i][j] = String.valueOf(maps[i].charAt(j));
if (!map[i][j].equals("X")) {
starts.add(new Integer[] { i, j });
landc+=1;
}
}
}
if(landc==0){
return new int[]{-1};
}
Arrays.stream(map).forEach(row -> System.out.println(Arrays.toString(row)));
System.out.println("starts: " +
starts.stream()
.map(Arrays::toString)
.toList());
List<Integer[]> road = new LinkedList<>();
List<Integer>foods=new LinkedList<>();
for (Integer[] start : starts) {
boolean exists = road.stream()
.anyMatch(r -> r[0].equals(start[0]) && r[1].equals(start[1]));
if (exists) {
System.out.println("이미다녀온경로");
continue;
}
int re= bfs(start, map, road);
System.out.println("식량총합: "+re);
foods.add(re);
}
Collections.sort(foods);
System.out.println(foods);
answer = foods.stream()
.mapToInt(Integer::intValue)
.toArray();
return answer;
}
public static int bfs(Integer[] start, String[][] map, List<Integer[]> road) {
int re = 0;
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], Integer.parseInt(map[start[0]][start[1]])});
visited[start[0]][start[1]] = true;
printvisit(visited);
boolean arrive = false;
while (!queue.isEmpty()) {
System.out.println("위치 탐색 예정 큐" +
queue.stream()
.map(Arrays::toString)
.toList());
Integer[] index = queue.poll();
Integer wid = index[1];
Integer hig = index[0];
re += Integer.parseInt(map[hig][wid]);
System.out.println("현재좌표: " + hig + "," + wid+"식량합: "+re);
if (wid == mw && hig == mh) {
System.out.println("끝에도착");
arrive = true;
break;
}
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) {
System.out.println("오른쪽전진: " + hig + "," + right);
String flg = map[hig][right];
System.out.println("전진값: " + flg);
if (!flg.equals("X") && !visited[hig][right]) {
System.out.println("O이므로 위치 저장가능");
road.add(new Integer[] { hig, right });
visited[hig][right] = true;
printvisit(visited);
queue.offer(new Integer[] { hig, right, re });
}
}
if (left >= 0) {
System.out.println("왼쪽전진: " + hig + "," + left);
String flg = map[hig][left];
System.out.println("전진값: " + flg);
if (!flg.equals("X") && !visited[hig][left]) {
System.out.println("O이므로 위치 저장가능");
road.add(new Integer[] { hig, left });
visited[hig][left] = true;
printvisit(visited);
queue.offer(new Integer[] { hig, left, re });
}
}
if (up >= 0) {
System.out.println("위쪽전진: " + up + "," + wid);
String flg = map[up][wid];
System.out.println("전진값: " + flg);
if (!flg.equals("X") && !visited[up][wid]) {
System.out.println("O이므로 위치 저장가능");
road.add(new Integer[] { up, wid });
visited[up][wid] = true;
printvisit(visited);
queue.offer(new Integer[] { up, wid,re });
}
}
if (down <= mh - 1) {
System.out.println("아래쪽전진: " + down + "," + wid);
String flg = map[down][wid];
System.out.println("전진값: " + flg);
if (!flg.equals("X") && !visited[down][wid]) {
road.add(new Integer[] { down, wid });
System.out.println("O이므로 위치 저장가능");
visited[down][wid] = true;
printvisit(visited);
queue.offer(new Integer[] { down, wid,re });
}
}
}
return re;
}
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피드백
-starts의 좌표마다 road를 처음부터 검색하므로, 지도 크기가 커질수록 비효율적이야.
전체 지도에서 visited 배열을 딱 한 번 만들고, 모든 BFS가 공유하면 돼.
배운점느낀점
-와 예전에는 dfs/bfs 문제보고 전혀 이해를 못했는데
지금은 코드는 좀 미숙하지만 잘 돌리고 있다 재밌다.
gpt 말대로 그냥 visited를 상위에 두고 써도 되는 문제였다
어차피 방문한 섬은 방문하지 않으면 되니까