- 소요시간 : 2시간 20분
- 문제 사이트 : 백준
- 문제 수준 : 골드 3
- 문제 유형 : 구현, 브루트포스 알고리즘, 시뮬레이션
- 다른 사람의 풀이를 참고 했는가 ? : X
- 문제 링크 : https://www.acmicpc.net/problem/17779
- 푼 날짜 : 2023.05.02
1. 사용한 자료구조 & 알고리즘
dfs, 브루트포스 알고리즘, 구현, 시뮬레이션
2. 사고과정
문제를 보고 이해하는 데에만 20분이 걸렸다.
이해한 뒤에는 어떤 알고리즘을 쓸까 고민했는데
N이 20밖에 안됐다.
N * N 의 map 이 있을 때 여기서 모든 좌표에서, 1~N-1 개의 d1,d2 를 각각 구해보기로 했다.
그렇다는 것은 브루트포스 알고리즘 문제라고 생각했다.
O(N^4) 여도 , O(N^5) 여도 풀 수 있는 문제였고, 결국 모든 경우의 수를 다 따져보기로 했다.
5번 선거구의 테두리를 정해주는 것은 그래도 꽤 금방했다.
5번 선거구 내의 사람들을 어떻게 나타내 줄 수 있을까를 고민해봤을 때 ,
그냥 위 사진에서 칠해진 곳 내부의 아무 좌표에서나 dfs 를 돌려주면 5가 모두 표시될 것이라고 생각했다.
하지만 그것은 오산이었고 이로 인해 1시간 가량을 소비했다 . ㅠ.ㅠ
이것이 해당하지 않는 경우는
위와 같은 경우였다. 빨간 좌표에서 4방향 dfs를 수행해도, 다른 빨간 좌표에 닿지 않는다. 계속 결과가 이상하게 나와서 이 오류를 찾는 것이 힘들었다.
그래서 이를 해결하기 위해 내린 결론은, 나올 수 있는 모든 내부의 테두리 좌표에서 dfs 를 수행하는 것이다.
위 사진으로 본다면 모든 빨간 좌표에서 dfs 를 수행하는 것이 되겠다.
이를 통해 문제를 해결했다.
3. 풀이과정
- (0,0,0,0) ~ (N-1,N-1,N-1,N-1) 의 브루트포스 알고리즘 수행. 모든 경우를 다 따져봄.
- 가장 테두리의 5번 선거구 사람들의 좌표를 구함
- 5번 선거구 내부 사람들에 대해 dfs를 수행해서 5번 선거구 사람 여부인지 true 로 처리함
- 1,2,3,4 번 선거구 사람들에 대해서 가장 위, 아래, 왼쪽, 오른쪽 좌표를 알고 있으므로 그 사각형 범위 내에서, 5번 선거구사람의 위치가 포함되지 않는 곳을 구해서 더해준다.
- 1~5번 선거구 사람들에 대해서 정렬하고, 가장 큰 값과 작은 값을 빼준다.
- 5번 작업이 일어날 때마다 갱신한다.
4. 소스코드
import java.util.*;
import java.io.*;
public class Main{
static int map[][];
static boolean five[][];
static int dy[] = {0,0,-1,1};
static int dx[] = {-1,1,0,0};
static int person[]=new int[5];
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb=new StringBuilder();
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
map=new int[N][N];
for(int i=0;i<N;i++) {
st=new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=0;i<N-1;i++) {
for(int j=0;j<N-1;j++) {
bruteforce(i,j);
}
}
System.out.println(min);
}
public static void bruteforce(int y,int x) {
for(int i=1;i<map.length;i++) {
for(int j=1;j<map.length;j++) {
cal(y,x,i,j);
}
}
}
public static void cal(int y,int x,int d1,int d2) {
//범위 넘어가면 조기종료
if((x-d1)<0) return;
if((x+d2)>=map.length) return;
if((y+d1+d2)>=map.length) return;
//5번 선거구 사람들이 위치한 좌표의 테두리를 표시
//left,right,top,bottom은 가장 왼쪽, 오른쪽, 위, 아래의 좌표를 저장함.
five=new boolean[map.length][map.length];
for(int i=0;i<d2;i++)
five[++y][++x] =true;
int right[]= {y,x};
for(int i=0;i<d1;i++)
five[++y][--x] =true;
int bottom[] = {y,x};
for(int i=0;i<d2;i++)
five[--y][--x] =true;
int left[] = {y,x};
for(int i=0;i<d1;i++)
five[--y][++x] =true;
int top[]= {y,x};
// 테두리 내부의 5번 선거구 내의 사람들에 대해
// 모든 좌표에서 방문한 적이 없다면 dfs를 수행.
int temp1 = top[0]+1;
int temp2 = top[1];
if(!five[temp1][temp2]) {
while(true) {
dfs(temp1,temp2);
if(temp2-1==left[1]) break;
temp1++;
temp2--;
}
}
temp1 = left[0];
temp2 = left[1]+1;
if(!five[temp1][temp2]) {
while(true) {
dfs(temp1,temp2);
if(temp1+1==bottom[0]) break;
temp1++;
temp2++;
}
}
temp1 = bottom[0]-1;
temp2 = bottom[1];
if(!five[temp1][temp2]) {
while(true) {
dfs(temp1,temp2);
if(temp2+1==right[1]) break;
temp1--;
temp2++;
}
}
temp1 = right[0];
temp2 = right[1]-1;
if(!five[temp1][temp2]) {
while(true) {
dfs(temp1,temp2);
if(temp1-1==top[0]) break;
temp1--;
temp2--;
}
}
//각 선거구 인원들을 세어줌
countMap(left,right,top,bottom);
}
public static void countMap(int left[],int right[],int top[],int bottom[]) {
int leftY=left[0]; int leftX=left[1];
int rightY=right[0]; int rightX=right[1];
int topY=top[0]; int topX=top[1];
int bottomY=bottom[0]; int bottomX=bottom[1];
person = new int[5];
//해당 구역에서 5번 선거구 사람이 아니라면 1번 선거구 사람임.
for(int i=0;i<leftY;i++) {
for(int j=0;j<=topX;j++) {
if(!five[i][j]) {
person[0] +=map[i][j];
}
}
}
//해당 구역에서 5번 선거구 사람이 아니라면 2번 선거구 사람임.
for(int i=0;i<=rightY;i++) {
for(int j=topX+1;j<map.length;j++) {
if(!five[i][j]) {
person[1] +=map[i][j];
}
}
}
//해당 구역에서 5번 선거구 사람이 아니라면 3번 선거구 사람임.
for(int i=leftY;i<map.length;i++) {
for(int j=0;j<bottomX;j++) {
if(!five[i][j]) {
person[2] +=map[i][j];
}
}
}
//해당 구역에서 5번 선거구 사람이 아니라면 4번 선거구 사람임.
for(int i=rightY+1;i<map.length;i++) {
for(int j=bottomX;j<map.length;j++) {
if(!five[i][j]) {
person[3] +=map[i][j];
}
}
}
//5번 선거구 표시가 된 좌표에서, 5번 선거구 사람의 합을 더해줌
for(int i=0;i<map.length;i++) {
for(int j=0;j<map.length;j++) {
if(five[i][j]) person[4] +=map[i][j];
}
}
//정렬함
Arrays.sort(person);
//가장 많은 사람이 있는 선거구에서, 가장 적은 사람이 있는 선거구 인원을 뺌
int val = person[4] - person[0];
//최솟값 갱신.
min = Math.min(val,min);
}
//dfs 수행
public static void dfs(int y,int x) {
five[y][x]=true;
for(int i=0;i<4;i++) {
int nextY=y+dy[i];
int nextX=x+dx[i];
if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length)
continue;
if(five[nextY][nextX])
continue;
dfs(nextY,nextX);
}
}
}
5. 결과
684 ms 가 내 코드,
472 ms 가 정답이 된 후 다른 사람의 코드를 제출한 것이다.
6. 회고
dfs를 하는 것 까지는 비록 결과가 안 좋았어도 그 사고 자체는 나쁘지 않았다고 생각한다.
하지만, dfs를 한 좌표에서만 처리하면 안 된다는 것을 알았을 때, 그렇다면 여기서는 dfs 말고 다른 방법으로 선거구 사람들을 구하는 유연한 사고가 필요해 보인다.
계속 시간복잡도 측면에서도 안 좋고, 조건을 떠올려 내기도 쉽지 않은 내부 공간에서의 dfs를 고집하다 보니 걸린 시간이 늘어났다.
실제로 다른 사람 풀이를 봐도 테두리 표시까지는 비슷하게 했으니, 1,2,3,4 번 선거구 인원들을 다른 방식으로 구했는데, 코드가 간결하고 유연해 보였다.
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212
