반응형
🔺 문제
🔺 코드
- 틀림
더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
import java.util.*;
import java.io.*;
public class Main {
static int[] dx = {0, 0, -1, 1, -1, -1, 1, 1};
static int[] dy = {1, -1, 0, 0, -1, 1,-1, 1};
static int N, M;
static int[][] map;
static boolean[][] visited;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N + 1][M + 1];
visited = new boolean[N + 1][M + 1];
// 입력 받기
for(int i = 1 ; i <= N ; i++) {
st = new StringTokenizer(br.readLine()," ");
for(int j = 1 ; j <= M ; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// 각 점마다 BFS 수행
for(int i = 1 ; i <= N ; i++) {
for(int j = 1 ; j <= M ; j++) {
if(map[i][j] == 1) {
visited[i][j] = true;
bfs(i, j);
visited[i][j] = false;
}
}
}
System.out.println(min + 1);
}
static void bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {x, y});
while(!queue.isEmpty()) {
int[] now = queue.poll();
for(int d = 0 ; d < 8 ; d++) {
int curX = now[0] + dx[d];
int curY = now[1] + dy[d];
if(curX < 1 || curX > N || curY < 1 || curY > M) continue;
if(map[curX][curY] == 1) {
min = map[x][y];
return;
}
if(!visited[curX][curY]) {
if(map[curX][curY] == 0) {
queue.offer(new int[] {curX, curY});
map[curX][curY] = Math.max(map[curX][curY], map[now[0]][now[1]] + 1);
}
}
}
}
}
}
|
cs |
- 정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
import java.util.*;
import java.io.*;
public class Main {
static int[] dx = {0, 0, -1, 1, -1, -1, 1, 1};
static int[] dy = {1, -1, 0, 0, -1, 1,-1, 1};
static int N, M, answer;
static int[][] map;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N + 1][M + 1];
// 입력 받기
for(int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine()," ");
for(int j = 0 ; j < M ; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// 각 점마다 BFS 수행 (브루트포스)
for(int i = 0 ; i < N ; i++) {
for(int j = 0 ; j < M ; j++) {
if(map[i][j] == 1) continue;
answer = Math.max(answer, bfs(i, j)); // 📍 모든 거리 중 최댓값 도출 📍
}
}
System.out.println(answer);
}
static int bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {x, y, 0});
// 🔔🔔 매 좌표마다 bfs 돌리니까 visited 배열 새롭게 선언 !! 🔔🔔
visited = new boolean[N + 1][M + 1];
visited[x][y] = true;
while(!queue.isEmpty()) {
int[] now = queue.poll();
for(int d = 0 ; d < 8 ; d++) {
int newX = now[0] + dx[d];
int newY = now[1] + dy[d];
int newDistance = now[2] + 1; // 🔔 거리도 저장해두자 🔔
if(newX < 0 || newX >= N || newY < 0 || newY >= M) continue;
if(visited[newX][newY]) continue;
if(map[newX][newY] == 1) {
return newDistance;
}
queue.offer(new int[] {newX, newY, newDistance});
visited[newX][newY] = true;
}
}
return 0;
}
}
|
cs |
✅ 해결 아이디어
✔ BFS
-각 좌표마다 값이 0일 때 BFS 수행!
💥 유의사항
• 각 좌표마다 값이 0일 때 BFS를 수행하므로, 매번 visited 배열을 초기화해야 함.
🔺 다른 풀이들
- 헐 내가 첨에 생각했던 방향 그대로 문제 푸셨음!! 그냥 while문 끝나기 직전에 cnt ++ 한 줄만 더 해주면 되는 거여씀!
나도 구현을 더 연습해야겄다,,,하하
- (x 좌표, y 좌표, 거리) 이렇게 세 가지 값을 저장하는 클래스를 따로 만들어서 푼 풀이
- 입력 받음과 동시에 입력받은 값이 1일 때 큐에 추가하는..
💬 느낀 점
bfs 여러번 수행할 때는 반드시 매번 visited 배열 초기화해주기!
사실 Node 클래스 따로 안 만들어 쓰려고 저렇게 Queue 에 int배열 선언해서 썼당...ㅋㅋ
근데 여기서 거리값 저장을 따로 안 함....
어떻게 저장해야 할까.. 싶었는데... 변수 하나만 더 추가해주면 되는 거여씀
거리 저장 방법이 다양한데
이 중에서 제일 편한 거 하나만 잘 써먹으면 될 거 같음
쫄지 말고!!
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 240507 |
(+240507 2회독 : 125976KB, 440ms)
코드 확인하기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
import java.util.*;
import java.io.*;
public class Main {
static int[] dx = {-1,1,0,0, -1,-1,1,1};
static int[] dy = {0,0,-1,1, -1,1,-1,1};
static int N,M;
static int[][] board;
static boolean[][] visited;
static int max = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
board = new int[N][M];
for(int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0 ; j < M ; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
// 1이 아닌 모든 점에서 BFS 수행
for(int i = 0 ; i < N ; i++) {
for(int j = 0 ; j < M ; j++) {
if(board[i][j] == 1) continue;
max = Math.max(max, bfs(i, j));
}
}
System.out.println(max);
}
private static int bfs(int x, int y) {
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] {x, y, 0});
// 방문 표시 배열 매번 새로 초기화해야 함
visited = new boolean[N][M];
visited[x][y] = true;
while(!q.isEmpty()) {
int[] now = q.poll();
for(int d = 0 ; d < 8 ; d++) {
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if(visited[nx][ny]) continue;
// 다음 점이 1이면, 거리 출력하고 종료
if(board[nx][ny] == 1) {
return now[2] + 1;
}
// 그게 아니라면, 큐에 점 추가해 마저 이동
visited[nx][ny] = true;
q.add(new int[] {nx, ny, now[2] + 1});
}
}
return 0;
}
}
|
cs |
(참고)
✔ 풀이 참고.... 덕분에 놓친 부분을 잡았읍니다.
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 1890번: 점프 (0) | 2023.05.28 |
---|---|
[백준/JAVA] 15486번: 퇴사 2 (0) | 2023.05.28 |
[백준/JAVA] 14226번: 이모티콘 (0) | 2023.05.27 |
[백준/JAVA] 13913번: 숨바꼭질 4 (0) | 2023.05.27 |
[백준/JAVA] 13549번: 숨바꼭질 3 (0) | 2023.05.26 |