티스토리 뷰
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
import java.io.*;
import java.util.*;
public class boj_2146 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static Queue<int[]> q = new LinkedList<>();
static boolean[][] v;
static int[][] a, map;
static int ans = Integer.MAX_VALUE;
static int N, islandCnt, nx, ny;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
input();
createMap();
findDistance();
System.out.println(ans);
}
static void input() throws IOException {
N = Integer.parseInt(br.readLine());
a = new int[N][N];
map = new int[N][N];
v = new boolean[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
a[i][j] = Integer.parseInt(st.nextToken());
}
}
}
static void createMap() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (a[i][j] == 1 && !v[i][j]) {
islandCnt++;
map[i][j] = islandCnt;
v[i][j] = true;
q.offer(new int[] {i, j});
while (!q.isEmpty()) {
int[] now = q.poll();
for (int k = 0; k < 4; k++) {
nx = now[0] + dx[k];
ny = now[1] + dy[k];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if (!v[nx][ny] && a[nx][ny] == 1) {
map[nx][ny] = islandCnt;
v[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
}
}
}
}
static boolean isEdge(int i, int j) {
for (int k = 0; k < 4; k++) {
nx = i + dx[k];
ny = j + dy[k];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if (map[nx][ny] == 0) return true;
}
return false;
}
static void findDistance() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 섬이면서 바다와 인접한 경우만 탐색이 필요
if (map[i][j] != 0 && isEdge(i, j)) {
v = new boolean[N][N];
q.offer(new int[] {i, j, 0});
int landNum = map[i][j];
while (!q.isEmpty()) {
int[] now = q.poll();
int dist = now[2];
for (int k = 0; k < 4; k++) {
nx = now[0] + dx[k];
ny = now[1] + dy[k];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
// 다른 섬 발견
if (map[nx][ny] != 0 && map[nx][ny] != landNum) {
ans = Math.min(ans, dist);
}
// 바다일 경우
if (map[nx][ny] == 0 && !v[nx][ny]) {
v[nx][ny] = true;
q.offer(new int[] {nx, ny, dist + 1});
}
}
}
}
}
}
}
}
|
cs |
- 1차 실패
- 오래 걸려서 근접했으나 아쉽다.
- 메소드가 한 가지 일만 하도록 세분화 시키자.
- 할 수 있는거도 복잡하니까 더 어려워진다.
1. 입력 받은후 섬에서 다른섬이랑 구분이 어려움 -> createMap 으로 각자 섬마다 고유 번호를 붙여줌
2. 탐색을 돌때 섬의 모든 부분에서 돌 필요 없이 바다와 인접해있는 부분에서만 돌면됨 -> isEdge 로 판별
3. findDistance로 탐색 시작
-> 각 부분에서 방문체크 필요한 v 새로 생성
-> 다른 섬 발견 했을경우 ans를 최솟값으로 수정
-> 바다일경우에는 계속 dist 증가
'PS > boj' 카테고리의 다른 글
boj)11724 - 연결 요소의 개수 (0) | 2020.11.02 |
---|---|
boj)5014 - 스타트링크 (0) | 2020.11.02 |
boj)13023 - ABCDE (0) | 2020.10.29 |
boj)2206 - 벽 부수고 이동하기 (0) | 2020.10.24 |
boj)2573 - 빙산 (0) | 2020.10.24 |
링크
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- 프로그래머스
- 이펙티브자바
- 백준
- REST API
- 프로그래머스 SQL
- 김영한 JPA
- JPA 연관관계 매핑
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 김영한 http
- Spring Security
- JS 딥다이브
- HTTP 완벽가이드
- 이펙티브자바 아이템59
- java
- js promise
- HTTP 완벽 가이드
- 킹수빈닷컴
- ㅇㄷㅇㅈ
- dreamcoding
- 이펙티브자바 아이템60
- js api
- GCP
- js array
- BOJ
- 드림코딩
- 백기선 스터디
- 모던자바스크립트
- 이펙티브자바 스터디
- 패스트캠퍼스 컴퓨터공학 완주반
- http
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함