https://programmers.co.kr/learn/courses/30/lessons/1844
문제 입출력 예
BFS를 활용하여 푸는 문제이다.
마지막 상대 진영까지 가지 못할 경우 -1을 return 해주는 부분만 잘 처리해주면 무난한 문제
더보기
import java.util.*;
class Solution {
static int n,m;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
public int solution(int[][] maps) {
int answer = 0;
n = maps.length;
m = maps[0].length;
answer = BFS(maps);
return answer;
}
public int BFS(int[][] maps){
Queue<Point> q = new LinkedList<Point>();
q.add(new Point(0,0));
int cnt = 1;
boolean[][] visited = new boolean[n][m];
while(!q.isEmpty())
{
int size = q.size();
for(int sz = 0; sz<size;sz++)
{
Point p = q.poll();
int x = p.x;
int y = p.y;
if(x == n-1 && y == m-1){
return cnt;
}
for(int cycle = 0; cycle<4;cycle++)
{
int cx = x+dx[cycle];
int cy = y+dy[cycle];
if(0<=cx && cx<n && 0<=cy && cy<m && maps[cx][cy] == 1 && !visited[cx][cy])
{
visited[cx][cy]=true;
q.offer(new Point(cx,cy));
}
}
}
cnt++;
}
return -1;
}
}
class Point
{
int x;
int y;
Point(int x, int y){
this.x = x;
this.y = y;
}
}
'PS' 카테고리의 다른 글
[BOJ]14502번: 연구소 (0) | 2021.06.18 |
---|---|
[BOJ]16234번: 인구 이동 (0) | 2021.06.16 |
[Programmers]LV2 - 예상대진표 (0) | 2021.06.14 |
[BOJ]17144번 : 미세먼지 안녕! (0) | 2021.06.14 |
[BOJ] 1958번: LCS 3 (0) | 2021.06.03 |