인프런 커뮤니티 질문&답변
작성한 질문수
BFS 게임 맵 최단거리 문의
작성
·
238
1
안녕하세요 기존에 BFS를 응용해서 타사이트중에
최단거리를 찾는문제에서 위,아래,오른쪽을 체크하는 방법을
몰라서 아래와 같이 막혔습니다. ㅠㅠ
오늘 10시간동안 골머리 앓다가 결국 문의 올립니다 ㅠ
해당 링크와 작성한 소스는 아래와 같습니다.
https://programmers.co.kr/learn/courses/30/lessons/1844
import java.util.LinkedList;
import java.util.Queue;
public class GameMapTest {
int m, n = 0; // 가로 세로를 구하기 위해 셋팅
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; // 오른쪽, 왼쪽, 위, 아래
int size = 0;// 칸의 개수
public int solution(int[][] grid) {
int answer = 0;
if(grid == null || grid.length == 0) {
return answer -1;
}
m = grid.length; // 행 길이 4
n = grid[0].length; // 열 길이 5
int maxCnt = 0;
int [][] visited = new int[m][n];
for(int i=0; i<m;i++) { //행렬보기
for(int j=0;j<n;j++) {
System.out.print(grid[i][j]);
}
}
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if(grid[i][j] == 1) {
size = 1;
bfs(grid, i, j, visited); // 0 만들기
if(maxCnt < size) {
maxCnt = size;
}
}
}
}
answer = maxCnt;
return answer;
}
public int bfs(int[][] grid, int x, int y, int[][] visited) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {x, y}); // 0, 0 으로 초기화해 버리기
// 오, 왼, 위 ,아래
while(!queue.isEmpty()) {
int[] point = queue.poll();
// 사방으로 조회
for(int[] dir : dirs) {
int x1 = point[0] + dir[0];
int y1 = point[1] + dir[1];
// 1. 마이너스 좌표 체크 x1 >= 0 && y1 >= 0
// 2. m*n 범위 체크 m > x1 && n > y1
// 3. grid[x1][y1] == 1
if(x1 >= 0 && y1 >= 0 && m > x1 && n > y1 && grid[x1][y1] == 1) {
if (!queue.isEmpty()) size++;
grid[x1][y1] = 0;
queue.offer(new int[]{x1, y1});
}
}
}
return size;
}
답변 3
2
안녕하세요~
열심히 하셔서 좋은 결과가 나올거 같습니다. 화이팅~~
bfs/dfs에 꽂히셔서 다행입니다. 축하드립니다. 그거 숙달되면 다른 문제는 쉽게 보입니다.
그리고 꼭 나오기 때문에 풀면 무조건 가산점입니다.
이런류의 문제는 신입이 풀면 거의 합격, 경력에서는 무조건 합격되는 문제입니다.
물론 응용되서 나오겠죠 ^^;
일단 아래처럼 풀어보시면 답이 나옵니다. 저번꺼 기본 뼈대에다가 응용부분만 고쳤습니다.
이런식으로 4-5개 연습하면 되실거여여~~제 강의로 응용해야 쉽게 보일겁니다.
다른분들이 만든 소스는 그 사람들의 철학과 생각이 녹아 있어서 , 다시 이해해야합니다.
저는 이부분을 공식화해서 초보자,중급자들이 빠르게 이해하도록 돕고 싶습니다.
나중에 완전 응용된 다른 문제를 강의로 만들어 보겠습니다~~
package bfs;
import java.util.*;
public class Basic_bfs03 {
public static void main(String[] args) {
Basic_bfs03 a = new Basic_bfs03();
int[][] grid =
{{1,0,1,1,1}
,{1,0,1,0,1}
,{1,0,1,1,1}
,{1,1,1,0,1}
,{0,0,0,0,1}};
int result = a.solution(grid);
System.out.println("result: " + result);
// System.out.println(Arrays.toString(a.solution(grid)));
}
int count = 0;
int[][] visited;
int[][] dirs = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
int m=0, n=0;
public int solution(int[][] grid) {
m = grid.length;
n = grid[0].length;
visited = new int[m][n];
// for (int i = 0; i < m; i++) {
// for (int j = 0; j < n; j++) {
// if (grid[i][j]==0) {
// continue;
// }
// }
// }
int thisAreaSize = bfs(grid, 0, 0, visited);
System.out.println("======thisAreaSize: "+thisAreaSize);
return thisAreaSize;
}
public int bfs(int[][] grid, int i, int j, int[][] visited) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] { i, j }); // first start queue
// System.out.println("i: "+i+" j "+j);
// visited[i][j] = true;
visited[i][j] = 1;
// int thisNumAreaSize = 0;
while (!queue.isEmpty()) {
int[] point = queue.poll();
// System.out.println("thisNumAreaSize: "+thisNumAreaSize);
for (int[] dir : dirs) {
int newX = point[0] + dir[0];
int newY = point[1] + dir[1];
if (newX >= 0 && newY >= 0 && newX < m && newY < n) {
System.out.println("grid[i][j] "+grid[i][j] +" grid[newX][newY] "+grid[newX][newY]);
if (visited[newX][newY] <=0 && grid[newX][newY] !=0 ) {
queue.add(new int[] { newX, newY });
visited[newX][newY] = visited[point[0]][point[1]]+1;
}
}
}
}
return visited[m-1][n-1] == 0 ? -1 : visited[m-1][n-1];
}
}
1
헉 너무 감사합니다.
"일단 아래처럼 풀어보시면 답이 나옵니다. 저번꺼 기본 뼈대에다가 응용부분만 고쳤습니다.
이런식으로 4-5개 연습하면 되실거여여~~제 강의로 응용해야 쉽게 보일겁니다.
다른분들이 만든 소스는 그 사람들의 철학과 생각이 녹아 있어서 , 다시 이해해야합니다.
저는 이부분을 공식화해서 초보자,중급자들이 빠르게 이해하도록 돕고 싶습니다."
- 말씀대로 이미 선생님께서 알려주신 공식으로 보다가 다른 걸 참고하려니까 더 모르겠더라구요.. 리셋하는 기분..ㅠㅠ -
다른 유료스터디도 하고 있지만, 피드백으로 새롭게 짜세요라는 식으로 대충 달아주고 응용이 잘안됐는데
선생님처럼 BFS 기존공식 바탕으로 응용해주셔서 1.5일동안 고민했던게
해결이 된거같습니다 ㅠㅠ BFS/DFS 달인이 되는 그날까지 풀어볼게요~
진심으로 감사합니다!!
0