1. 문제 링크 및 문제
https://www.acmicpc.net/problem/14500
2. 해결 방법 생각해보자 ...
DFS를 사용하면 된다.
근데 저렇게 다양한 도형을 회전,대칭 다 어떻게 하냐!
는 한가지 상황만 예외처리 해주면, 일반 DFS 문제랑 똑같이 풀린다.
내가 너무 어렵게 생각했다
한 좌표 -> 상, 하, 좌, 우 로 좌표 이동
또 이 모든 좌표에서 -> 상, 하, 좌, 우 를 실행하면
문제에서 주어진 'ㅜ' 모양 빼고 모두 조건을 만족할 수 있다.
바로 백준 예시1 로 이해해보자
DFS(x 좌표, y좌표, 몇번째 스텝, 합 ) 을 적어준다.
출발은 0,0 부터 마지막 4,4 까지 모든 경우를 탐색
- 0,0 좌표 탐색 -> DFS(0,0,1,arr[0][0])
= ( x좌표 , y좌표, 첫번째 탐색, 합계 = 1)
- 갈 수 있는 경우의 수는 (0,1) (1,0) 이다. DFS(0,1) 로 가보자.
현재 합 : 3
2-1. (0,1) 에서 갈 수 있는 경우의 수는 (0,2) (1,1) 이다..
(0,2) 로 가보자.
2-1-1. (0,2) 에서 갈 수 있는 경우의 수는 (0,3) (1,2) 이다.
(0,3) 으로 가보자.
오! 그럼 우린 문제에서 주어진 이 형태로 합을 계산했다.
모든 도형이 4개로 이루어져 있으므로, step == 4 일 때 return 하자~!!
2-1-2. return 하면, (0,2) 에서 갈 수 있는 경우의 수는 (0,3) (1,2)
이때로 돌아가므로, (0,3) 은 방문했으니까 (1,2) 로 가보자.
오! 그럼 우린 또 문제에서 주어진 이 형태를 회전했을 때의 합을 구했다.
이런 식으로, DFS 를 통하여 우리는 주어진 도형의 모든 대칭, 회전의 경우의 수를 구할 수 있다.
한 도형 'ㅜ' 빼고!
왜냐?
'ㅜ'는 2번째 스텝에서 3->4 가 아닌, 2->3, 2->3 의 과정이다
따라서 step == 2 일 때는 예외처리를 하여
'2' 의 좌표를 보내주어야
2->3, 2->3 이 가능해진다.
아래는 코드이다.
근데 이제 TMI 를 지나면 있는...
글쓰는 거 보면 말은 많은데 코드에 주석이 없는 이유
어디선가 본건데 (본 건 많음) 주석이 없는 코드, 코드로도 충분해서 설명할 내용이 없는 코드야말로 좋은 코드라는 글을 본 이후로
최대한 주석에 의존하지 않고, 코드를 이해하기 쉽고 간결하게 짤려고 노력하고 있다!
둘 다 적절히 사용하는 것이 물론 최고이겠거니와..
점점 코드 길이가 길어지면서 내 코드가 좋은 코드인 지 , 아닌지 굉장히 궁금하다 ㅎㅎ
배울 수 있는 환경으로 가서 빨리 더 더 성장하고 싶다.
무조건 회사다니면 실력 늘거야! 라고 생각해서 입사하고..
회사 다닐 때는 주어진 업무를 처리하며 이거지 이거지 하면서 코딩 실력이 늘었다면,
퇴사하고 공부하고 있는 지금은 어떤 방향으로, 어떻게 공부해서, 어떤 개발자가 될 것 인지에 대해 생각할 수 있어서 좋은 것 같다
아이고.투머치 토커인 나는 또 코드에 주석이 없는 이유 적으려다 이까지나 와버렸네.. ㅎㅎ😅
3. 코드
import java.io.*;
import java.util.*;
public class Main {
static int N,M;
static int[][] arr;
static int[] dx = {-1,1,0,0},dy={0,0,-1,1};
static int MaxResult = 0, MaxValue = 0;
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());
arr = new int[N][M];
visited = new boolean[N][M];
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine());
for(int j=0;j<M;j++){
arr[i][j] = Integer.parseInt(st.nextToken());
MaxValue = Math.max(MaxValue, arr[i][j]);
}
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
visited[i][j] = true;
DFS(i,j,1,arr[i][j]);
visited[i][j] = false;
}
}
System.out.println(MaxResult);
}
public static void DFS(int x, int y,int step, int sum){
if(sum + (MaxValue)*(4-step) <= MaxResult) return;
if(step == 4 ){
MaxResult = Math.max(MaxResult, sum);
return ;
}
for(int i=0;i<4;i++){
int xx= x+dx[i];
int yy = y+dy[i];
if(xx<0 || xx>=N || yy<0 || yy>=M || visited[xx][yy]) continue;
if(step==2){
visited[xx][yy] = true;
DFS(x,y,step+1,sum+arr[xx][yy]);
visited[xx][yy] = false;
}
visited[xx][yy] = true;
DFS(xx,yy,step+1,sum+arr[xx][yy]);
visited[xx][yy] = false;
}
}
}
느낀점
처음에 저 주어진 5가지 형태로 모두 구현해야하나 ... ?
그럼 대칭, 회전까지 어떻게 하지...? 했는데 ...
구현하다가 도저히 못하겠어서 다른 분들의 풀이를 참고하였는데 두둥.
세상에나 마상에나. 이런 방법이
내가 알고 있는 DFS를 도형으로 표현하면 이렇구나 💡💡
라고 머리를 한 대 댕~ 맞은 기분이었다.
진짜.. 이 문제가 너무 어렵게 느껴졌는데
풀고 보니 정말 별 거 아닌 그냥 DFS 구현해봐라. 문제였다.
알고리즘 문제는 모든 문제가 그런 것 같다.
처음엔 진짜 이해안가고 어렵지만
지지고 볶아서 이해하고 또 똑같은 알고리즘 기법을 적용하는 문제들을 풀어나가다 보면
풀이과정이 머릿속에 그려지고 정리되고.. 글로도 정리해보고..
근데 이제 그 과정이 오래걸리긴 하지만
할 수 있다는 믿음을 갖고 꾸준히 풀어나가야겠다!
깨닫고 배운 게 너무 많은 문제였다!
문제 푸는 거 너무 재미써 ~~
(- 이 문제가 너무 어려웠던 나에게 해주는 말..)
