[Java] 54. Spiral Matrix - LeetCode daily challenge

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

Spiral Matrix - LeetCode

 
 
 

첫번째풀이

---

두통이 조금 심한 날이라 깊게 생각하기 싫었다.
처음 생각난게 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;
    }
}