[백준 18290, 자바] NM과 K (1)

→ 풀이 리뉴얼

alwaysbemoon.tistory.com/247

[백준 18290, 자바] NM과 K (1) renew

 

 

18290번: NM과 K (1)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main{
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine()," ");
    int N =Integer.parseInt(st.nextToken());
    int M =Integer.parseInt(st.nextToken());
    int K =Integer.parseInt(st.nextToken());

    int[][] square= new int[N][M];
    for(int r=0 ; r<N ; r++){
      StringTokenizer st2 = new StringTokenizer(br.readLine()," ");
      for(int c=0;c<M;c++){
        square[r][c] = Integer.parseInt(st2.nextToken());
      }
    }
    NMK2 nmk2 = new NMK2(N, M, K, square);
    nmk2.findMax(0, 0, 0, 0);
    int max = nmk2.getMax();
    bw.write(String.valueOf(max));
    bw.flush();

    br.close();
    bw.close();
  }
}
class NMK2{
  int N;
  int M;
  int K;
  int[][] square;
  boolean[][] visited;
  int max;

  final int[]dx = {0,-1,0,1,0};
  final int[] dy= {0,0,1,0,-1};

  NMK2(int N, int M , int K, int[][] s){
    this.N=N;
    this.M=M;
    this.K=K;
    square=s;
    visited = new boolean[N][M];
    max=-1234567890;
  }

  void findMax(int x, int y, int count, int sum){
    if(count>=K){
      max= Math.max(max,sum);
    }
    else{
      for(int px=x;px<N;px++){
        for(int py=y;py<M;py++){
          if(isValid(px,py)){
            visited[px][py]=true;
            findMax(x, y, count+1, sum+square[px][py]);
            visited[px][py]=false;
          }
        }
      }
    }
  }
  boolean isValid(int x, int y){
    boolean isValid=true;
    for(int i= 0 ;i<dx.length;i++){
      int tempX= x+dx[i];
      int tempY =y+dy[i];

      if(tempX>=0 && tempX<N && tempY>=0 && tempY<M){
        if(visited[tempX][tempY]){
          isValid=false;
        }
      }
    }
    return isValid;
  }

  int getMax(){
    return max;
  }

}

 

* REVIEW

1. 처음 했던 잘못된 접근

- 현재 셀을 기준으로 상하좌우 셀을 방문하여 방문한 숫자가 3이상이면 max(max,sum) 

- 인프런에 findMaze 방식으로 생각. 전체 셀을 방문하는게 아닌 한 셀을 기준으로 

 

2. 재귀

- 현재 셀이 유효한 셀이면 현재 셀 & 인접셀을 방문했다고 처리후(visited[x][y]= true) , 함수가 return 되면 방문 해제 (visited[x][y]=false) 

 

- 이렇게 하게되면 

위의 경우에, (0,1)을 방문하고 (1,0)을 방문한 후, (1,0)과 주변 셀을 해제할때 (1,0)도 해제가 된다.

- 방문 처리를 하는게 아니라 현재 셀을 기준으로 주변에 방문한 셀이 있는지 확인하는 방법으로 하면 된다. 

 

3. 시간 줄이기

-  우, 하 방향으로만 방문하기