• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

BFS 게임 맵 최단거리 문의

21.02.19 23:41 작성 조회수 153

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

Sung Rak님의 프로필

Sung Rak

질문자

2021.02.20

헉 너무 감사합니다.

"일단 아래처럼 풀어보시면 답이 나옵니다. 저번꺼 기본 뼈대에다가 응용부분만 고쳤습니다.

이런식으로 4-5개 연습하면 되실거여여~~제 강의로 응용해야 쉽게 보일겁니다.

다른분들이 만든 소스는 그 사람들의 철학과 생각이 녹아 있어서 , 다시 이해해야합니다.

저는 이부분을 공식화해서 초보자,중급자들이 빠르게 이해하도록 돕고 싶습니다."

- 말씀대로 이미 선생님께서 알려주신 공식으로 보다가 다른 걸 참고하려니까 더 모르겠더라구요.. 리셋하는 기분..ㅠㅠ -

다른 유료스터디도 하고 있지만, 피드백으로 새롭게 짜세요라는 식으로 대충 달아주고 응용이 잘안됐는데

선생님처럼 BFS 기존공식 바탕으로 응용해주셔서 1.5일동안 고민했던게

해결이 된거같습니다 ㅠㅠ BFS/DFS 달인이 되는 그날까지 풀어볼게요~ 

진심으로 감사합니다!!

 

0

네 ~ 열심히 하시니까 

좋은 결과 얻으 실겁니다.

감사합니다~