[백준] S17086

https://www.acmicpc.net/problem/17086

17086번: 아기 상어 2

 

# 아이디어

1. N*M 크기의 map에서의 모든 자리에서 검색을 한번씩 한다.

2. 각 자리에서 가장 가까운 상어를 찾는다.

3. 각 자리에서 가장 가까운 상어와의 거리를 안전거리의 최댓값으로 저장한다.

4. N*M번 반복하는 검색을 하며 안전거리의 최댓값을 비교하며 업데이트 한다.

 

# 오답

처음에는 bfs로 하려다가 2차원 배열로 구성된 map을 어떻게 검색해야 할 지 모르겠어서 그나마 익숙한 dfs를 사용하기로 함.

package baekjoon;

import java.util.Scanner;

public class S17086 {

	public static int n;
	public static int m;

	public static int[][] map;
	public static int[][] visited;
	public static int distance = 0;
	public static int safeDistance = -1;

	public static int[] dx = { 0, -1, -1, -1, 0, 1, 1, 1 };
	public static int[] dy = { -1, -1, 0, 1, 1, 1, 0, -1 };

	public static void dfs(int x, int y) {
		if (x < 0 || y < 0 || x >= n || y >= m) {
			distance--;
			return;
		}

		if (map[x][y] == 1) {
			safeDistance = distance;
			distance--;
		}

		for (int i = 0; i < 8; i++) {
			distance++;
			if (visited[x][y] != 1) {
				visited[x][y] = 1;
				dfs(x + dx[i], y + dy[i]);
			}
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();

		map = new int[n][m];
		visited = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		int max = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				distance = 0;
				dfs(i, j);
				if (max < safeDistance) {
					max = safeDistance;
				}
			}
		}

		System.out.println(max);

		sc.close();

	}

}

아이디어는 맞는데 다시 생각해보니 dfs말고 bfs로 해야 거리 검색이 제대로 될 듯??? 아닌가???

 

# 블로그 참조

아직 블로그 안 보고 bfs 구현은 어려운 것 같다... ㅜㅠ 이전에 풀었는 백준 1260 문제를 참고하면서 구현하려 했으나 실패함 ㅠ

기존의 BFS 문제와 달리 Queue에 vertex만 넣는게 아니라, x좌표, y좌표, 이동한 거리 총 3가지를 배열로 구성하여 Queue에 저장하는 방식이다. 나머지는 동일하지만 Queue에 배열을 저장한다는 방식이 새로웠다.

 

Sol 1.

블로그 참조 살짝하고 코드 수정하였는데 왜 답이 다르게 나오는지...!!!

public static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		visited = new int[n][m];

		visited[x][y] = 1;
		q.offer(new int[] { x, y });

		while (!q.isEmpty()) {
			int[] pop = q.poll();

			for (int i = 0; i < 8; i++) {
				int newX = x + dx[i];
				int newY = y + dy[i];	

				if (newX < 0 || newY < 0 || newX >= n || newY >= m || visited[newX][newY] == 1) {
					continue;
				}

				visited[newX][newY] = 1;
				distance++;

				if (map[x][y] == 1) {
					safeDistance = distance;
					return;
				}

				q.offer(new int[] { newX, newY });

			}
		}

	}

디버깅 하다 보니 distance의 값이 이상하게 증가하는 것을 발견! 하나의 위치에서 8방향으로 움직이는데 이 모든 움직임이 하나의 distance로 계산되어 버림...

또, newX, newY를 계산할 때, x와 y를 계산식에 바로 사용한다면 (0,0)에서의 계산만 하는 것이다...

 

Sol 2.

이제 값이 제대로 출력되는거 같긴한데...

1씩 증가된 값이 출력된다.

		int max = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				bfs(i, j);
				if (max < safeDistance)
					max = safeDistance;
			}
		}

		System.out.println(max);

-> bfs 구현 구조상 시작하는 위치의 값이 1이면 이를 검사하지 못한다.

 

Sol 3.

해결~~!! 블로그 참조를 조금만 하려다 보니 헤맨 부분이 꽤 많았다 ㅠ.ㅠ

package baekjoon;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class S17086 {

	public static int n;
	public static int m;

	public static int[][] map;
	public static int[][] visited;
	public static int safeDistance = -1;

	public static int[] dx = { -1, -1, -1, 0, 1, 1, 1, 0 };
	public static int[] dy = { -1, 0, 1, 1, 1, 0, -1, -1 };

	public static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		visited = new int[n][m];

		visited[x][y] = 1;
		q.offer(new int[] { x, y, 0 });

		while (!q.isEmpty()) {
			int[] pop = q.poll();

			for (int i = 0; i < 8; i++) {
				int newX = pop[0] + dx[i];
				int newY = pop[1] + dy[i];
				int distance = pop[2] + 1;

				if (newX < 0 || newY < 0 || newX >= n || newY >= m || visited[newX][newY] == 1) {
					continue;
				}

				if (map[newX][newY] == 1) {
					safeDistance = distance;
					return;
				}

				q.offer(new int[] { newX, newY, distance });
				visited[newX][newY] = 1;

			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();

		map = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		int max = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 1)
					continue;
				bfs(i, j);
				if (max < safeDistance)
					max = safeDistance;
			}
		}

		System.out.println(max);

		sc.close();

	}

}

 

 

💯💯💯

bfs 구현 연습 꾸준히 하자...!!!

가장 처음에 문제를 봤을 때 bfs 자체의 개념까지 흔들렸다는..;;;