☀️ 문제 링크
🌻 문제 간단한 설명
- BFS 알고리즘을 사용하는 문제이다.
- 메모리 제한이 있기 때문에 무턱대고
System.out.println을 사용해선 안된다.- DFS, BFS는 거의 틀이 잡혀있기 때문에 문제를 많이 풀면 이해하기 쉬울 것이다.
⚡️ 풀이
🌝 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int Y;
static int X;
static int[] dy = {1, 0, -1, 0};
static int[] dx = {0, 1, 0, -1};
static int[][] map;
static boolean[][] isVisited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
Y = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
map = new int[Y][X];
isVisited = new boolean[Y][X];
for (int i = 0; i < Y; i++) {
map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
boolean flag = false;
int startY = 0, startX = 0;
for (int i = 0; i < Y; i++) {
if (!flag) {
for (int j = 0; j < X; j++) {
if (map[i][j] == 2) {
map[i][j] = 0;
flag = true;
startY = i;
startX = j;
break;
}
}
}
}
bfs(startY, startX);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
if (!isVisited[i][j] && map[i][j] == 1) {
sb.append(-1).append(" ");
} else {
sb.append(map[i][j]).append(" ");
}
}
sb.append("\n");
}
System.out.println(sb);
}
private static void bfs(int startY, int startX) {
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(startY, startX));
isVisited[startY][startX] = true;
while (!queue.isEmpty()) {
Point point = queue.poll();
int y = point.y;
int x = point.x;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= Y || nx >= X) {
continue;
}
if (!isVisited[ny][nx] && map[ny][nx] == 1) {
queue.add(new Point(ny, nx));
isVisited[ny][nx] = true;
map[ny][nx] = map[y][x] + 1;
}
}
}
}
static class Point {
int y;
int x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
}
}🌛 코드별 설명
시작 지점 설정 & 값 초기화
- 시작지점이 따로 정해져있지 않고 숫자 2가 있는곳에서 출발 한다.
- 또한 새로운
int[][]을 만들지 않고 덮어씌울 예정이라 값을0으로 초기화 했다.- 물론 새로운
answer[][]을 만들어서 해도된다.(해보니 통과함)
난 이게 편한듯
boolean flag = false;
int startY = 0, startX = 0;
for (int i = 0; i < Y; i++) {
if (!flag) {
for (int j = 0; j < X; j++) {
if (map[i][j] == 2) {
map[i][j] = 0;
flag = true;
startY = i;
startX = j;
break;
}
}
}
}
bfs(startY, startX);정답 출력
- 여기서 메모리 초과를 해서 시간이 오래 걸렸다.
원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.- 그래서 두 코드의 메모리의 차이를 알고 싶어서 찾아봤는데
메모리 차이가 거의 없다고 한다.하지만 실제 문제를 의도하고 출제를 하였다면 문제는 틀렸다. 최대한 메모리를 적게 사용하는 방법을 택해야겠다.
Before (메모리 초과)
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
if (!isVisited[i][j] && map[i][j] == 1) {
map[i][j] = -1;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < Y; i++) {
sb.append(Arrays.stream(map[i])
.mapToObj(String::valueOf)
.reduce((x, y) -> x + " " + y)
.orElse(""))
.append("\n");
}
System.out.println(sb);After (성공)
StringBuilder sb = new StringBuilder();
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
if (!isVisited[i][j] && map[i][j] == 1) {
sb.append(-1).append(" ");
} else {
sb.append(map[i][j]).append(" ");
}
}
sb.append("\n");
}
System.out.println(sb);BFS
- 전형적인 BFS 코드이다.
2(시작지점)지점을0으로 초기화를 해줬기 때문에 마지막에 이전의 칸의 값을+ 1해줬다.
private static void bfs(int startY, int startX) {
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(startY, startX));
isVisited[startY][startX] = true;
while (!queue.isEmpty()) {
Point point = queue.poll();
int y = point.y;
int x = point.x;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= Y || nx >= X) {
continue;
}
if (!isVisited[ny][nx] && map[ny][nx] == 1) {
queue.add(new Point(ny, nx));
isVisited[ny][nx] = true;
map[ny][nx] = map[y][x] + 1;
}
}
}
}🌞 끝으로
시간복잡도, 공간복잡도, 메모리를 계산하면서 풀려고 해야겠다. 아직까지 그 부분이 조금 부족한듯하다. (솔직히 잘 모름)
만약 구글링이 안 됐으면 거의 하루종일 못 풀었을 듯하다.
🙏