풀이

DFS를 이용해서, 해당 칸을 탐색할 수 있을 경우 탐색해서 모든 경우의수를 구한다음 최대값을 구하는 단순 DFS문제라고 생각했다.

class Solution {
	public static long max = -1;
	
    public long mostPoints(int[][] questions) {
       	if(questions.length==1) return questions[0][0];

        boolean[] bl = new boolean[questions.length];
        
        for(int i=0; i<questions.length; i++) {
        	dfs(questions[i][0], i, questions[i][1]+1, questions, bl);
        }        
    	return max;
    }
    
    public void dfs(long sum, int idx, int tmp, int[][] questions, boolean[] bl) {
    	if(idx >= questions.length) {
    		max = Math.max(max, sum);
    		return;
    	}    	
    	
    	for(int i=idx; i<questions.length; i++) {    		    		
    		if(tmp != 0) {
    			tmp--;
    			continue;
    		}
    		if(bl[i]) return;
    		bl[i]=true;
    		dfs(sum+questions[i][0], i+1, tmp+questions[i][1]+1, questions, bl);
    		bl[i]=false;
    	}
		max = Math.max(max, sum);
    }
}

분명 IDE의 콘솔에서는 정답이 출력되는데 왜 틀렸다고 하는지 모르겠다. 나는 100이 나오는데 ㅡㅡ

머리 환기시키고 재도전해봐야겠다..

https://leetcode.com/problems/spiral-matrix-ii/

풀이

방향에 대한 변수와, 한 칸씩 체크해줄 변수를 지정해 준 뒤, 카운팅만 잘 해주면 되는 문제였다.

class Solution {		
	
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int top = 0;
        int bottom = n-1;
        int left = 0;
        int right = n-1;
        int cnt = 1;
        while(cnt <= n*n) {
        	for(int i=left; i<=right; i++) {
        		matrix[top][i] = cnt;
        		cnt++;
        	}
        	top++;
        	  
        	for(int i=top; i<=bottom; i++) {
        		matrix[i][right] = cnt;
        		cnt++;
        	}
        	right--;
        	
        	for(int i=right; i>=left; i--) {
        		matrix[bottom][i] = cnt;
        		cnt++;
        	}
        	bottom--;
        	
        	for(int i=bottom; i>=top; i--) {
        		matrix[i][left] = cnt;
        		cnt++;
        	}
        	left++;
        	
        }
        return matrix;
    }
}

https://leetcode.com/problems/spiral-matrix/

첫번째풀이

두통이 조금 심한 날이라 깊게 생각하기 싫었다.
처음 생각난게 DFS, 두번째로 생각난건 while문으로 때려풀기였다.
하나하나 진행해보자

class Solution {		
	
    public List<Integer> spiralOrder(int[][] matrix) {    	
    	List<Integer> list = new ArrayList<>();    	
    	int sum = 0;
    	
    	for(int[] m : matrix) {
    		for(int n : m) {
    			sum++;
    		}
    	}
    	
    	dfs(list, matrix, 0, 0, sum);    	
    	return list;
    }
    
    public void dfs(List<Integer> list, int[][] matrix, int i, int j, int sum) {
    	if(sum == list.size()) return;
    	if(i < 0 || i >= matrix.length) return;
    	if(j < 0 || j >= matrix[0].length) return;
    	if(matrix[i][j]==-101) return;
    	
    	list.add(matrix[i][j]);
    	matrix[i][j] = -101;
    	
    	dfs(list, matrix, i, j+1, sum);
    	dfs(list, matrix, i+1, j, sum);
    	dfs(list, matrix, i, j-1, sum);
    	dfs(list, matrix, i-1, j, sum);    	
    }
}

 
재귀호출의 순서를 어떻게 바꿔도, 시계방향으로 한 방향씩 끝까지 탐색한 후에 다른방향으로의 탐색이 어려운 것 같다.
 

실패

두번째 풀이

그냥 while문안에 cnt와 idx를 올려가며 때려박아서 풀었다. 설명이 굳이 필요없다. 시계방향으로 돌리는 것을 직접 노가다로 구현..

import java.util.ArrayList;
import java.util.List;

class Solution {		
	
    public List<Integer> spiralOrder(int[][] matrix) {    	
    	List<Integer> list = new ArrayList<>();    	
    	int sum = matrix.length * matrix[0].length;   	
    	int cnt = 0;
    	int idx = 0; 
    	while(cnt<sum) {
    		for(int i=idx; i<matrix[0].length; i++) {
    			if(matrix[idx][i] != 101) {
    				list.add(matrix[idx][i]);
    				cnt++;
        			matrix[idx][i] = 101;
    			}
    		}
    		for(int i=idx; i<matrix.length; i++) {
    			if(matrix[i][(matrix[0].length-1)-idx] != 101) {
    				list.add(matrix[i][(matrix[0].length-1)-idx]);
    				cnt++;
    				matrix[i][(matrix[0].length-1)-idx] = 101;
    			}    			
    		}
    		for(int i=matrix[0].length-1; i>=idx; i--) {
    			if(matrix[(matrix.length-1)-idx][i] != 101) {    				
    				list.add(matrix[(matrix.length-1)-idx][i]);
    				cnt++;
    				matrix[(matrix.length-1)-idx][i] = 101;
    			}    			
    		}
    		for(int i=matrix.length-1; i>=idx; i--) {
    			if(matrix[i][idx] != 101) {
    				list.add(matrix[i][idx]);
    				cnt++;
    				matrix[i][idx] = 101;
    			}    			
    		}
    		idx++;
    	}
    	return list;
    }
}