반응형
https://www.acmicpc.net/problem/2468
틀린 접근법 (69%)
import java.io.*;
import java.util.*;
public class prac {
public static int[][] arr;
public static boolean[][] visited;
public static int n;
public static int[] dx = {0,1,0,-1};
public static int[] dy = {1,0,-1,0};
public static HashSet<Integer> hs = new HashSet<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
int max_v = 0;
for (int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for (int j=0; j<n; j++) {
int k = Integer.parseInt(st.nextToken());
arr[i][j] = k;
hs.add(k);
}
}
ArrayList<Integer> nums = new ArrayList<>(hs);
for (int t=0; t<nums.size(); t++) {
int h = nums.get(t);
int cnt = 0;
visited = new boolean[n][n];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (!visited[i][j] && arr[i][j] > h) {
visited[i][j] = true;
bfs(i,j,h);
cnt++;
}
}
}
max_v = Math.max(max_v,cnt);
}
System.out.println(max_v);
}
public static void bfs(int x, int y,int h) {
Queue<Node> q = new ArrayDeque<Node>();
q.add(new Node(x,y));
while (!q.isEmpty()) {
Node cur = q.poll();
for (int i=0; i<4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (check(nx,ny) && !visited[nx][ny]) {
if (arr[nx][ny] > h) {
q.add(new Node(nx,ny));
visited[nx][ny] = true;
}
}
}
}
}
public static boolean check(int x, int y) {
if (0 <= x && x < n && 0 <= y && y < n) return true;
else return false;
}
}
class Node{
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
해당 코드가 오답을 받았던 이유는 "강수량이 될 수 있는 범위를 모두 고려해주지 않음 + 문제를 제대로 읽지 않음" 입니다 !
문제에서 강수량이 될 수 있는 수가 정확히 나와있지는 않습니다. 저는 높이가 1이상 100이하라고 명시해줘서 당연히 강수량도 1부터 100까지의 수인줄 알았습니다. 하지만 비가 아예 안오는 경우도 있기 때문에 0부터 연속된 모든 수를 고려해야 합니다. (오답의 원인1)
하나 더 실수한 부분은 문제에서 주어진 높이만이 강수량이 될 수 있는게 아니라 강수량은 0부터 max_h 사이의 연속된 수 모두가 될 수 있다는 부분입니다. 만약 가장 높은 높이가 10일 경우, 강수량이 될 수 있는 수는 0부터 10까지입니다. 그렇기에 11가지 경우를 모두 확인해야 합니다 ! (오답의 원인2)
저는 바보같이 주어진 높이만 가능한 줄 알고 set으로 중복을 제거 하고 리스트로 바꿔서 인덱스별로 접근했습니다 ㅠ
수정된 코드
import java.io.*;
import java.util.*;
public class prac {
public static int[][] arr;
public static boolean[][] visited;
public static int n;
public static int[] dx = {0,1,0,-1};
public static int[] dy = {1,0,-1,0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
int max_v = 0;
int max_h = 0;
for (int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for (int j=0; j<n; j++) {
int k = Integer.parseInt(st.nextToken());
arr[i][j] = k;
max_h = Math.max(max_h, k);
}
}
for (int t=0; t<=max_h; t++) {
int cnt = 0;
visited = new boolean[n][n];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (!visited[i][j] && arr[i][j] > t) {
visited[i][j] = true;
bfs(i,j,t);
cnt++;
}
}
}
max_v = Math.max(max_v,cnt);
}
System.out.println(max_v);
}
public static void bfs(int x, int y,int h) {
Queue<Node> q = new ArrayDeque<Node>();
q.add(new Node(x,y));
while (!q.isEmpty()) {
Node cur = q.poll();
for (int i=0; i<4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (check(nx,ny) && !visited[nx][ny]) {
if (arr[nx][ny] > h) {
q.add(new Node(nx,ny));
visited[nx][ny] = true;
}
}
}
}
}
public static boolean check(int x, int y) {
if (0 <= x && x < n && 0 <= y && y < n) return true;
else return false;
}
}
class Node{
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
난이도는 실버1이지만 그래프 문제에서 꽤 괜찮은 문제였다고 생각합니다 ! 함정에 빠지지 않도록 항상 신경써야될 거 같습니다 !!
반응형