[LeetCode Medium] Spiral Matrix !! - BFS

class Solution {
	
	// 이동방향
	private static int[][] D = {{0,1}, {1,0}, {0,-1}, {-1,0}};
	
	// 노드 클래스
	static class Point{
		int row;
		int col;
		int dist;
		
		public Point(int row, int col, int dist) {			
			this.row = row;
			this.col = col;
			this.dist = dist;		
		}		
	}
	
	public static List<Integer> spiralOrder(int[][] matrix) {
        
		int m = matrix.length;		// 가로길이
		int n = matrix[0].length;	// 세로길이			
		int cnt = 0;	// 탐색횟수
		
		List<Integer> result = new ArrayList<Integer>();	// 결과
		boolean[][] visit = new boolean[m][n];	// 방문체크
		Queue<Point> queue = new LinkedList<Point>();	// 탐색용 큐
				
		queue.add(new Point(0, 0, 0));	// 시작 Point를 큐에 넣음 (0,0), 첫 이동은 D[0][0], D[0][1]
		
		while(!queue.isEmpty()) {
			Point point = queue.poll();	// 큐에서 꺼내서 확인
			int row = point.row;
			int col = point.col;			
			int dist = point.dist;
			
			visit[row][col] = true;	// 방문체크
			
            // 실제 작업 : 결과입력
            result.add(matrix[row][col]);
            cnt++;
			if(cnt == m * n) break;
			
			// 우선 이전 방향으로 이동해봄
			int nRow = row + D[dist][0];
			int nCol = col + D[dist][1];			
			if(nRow < 0 || nRow >= m || nCol < 0 || nCol >= n || visit[nRow][nCol]) {	
                // 범위를 벗어나거나 이미 방문했다면, 새로운 방향으로 이동
				dist++;
				if(dist == 4) dist = 0;
				nRow = row + D[dist][0];
				nCol = col + D[dist][1];
			}
			queue.add(new Point(nRow, nCol, dist));			
		}
						
		return result;
    }
}

 

- while안쪽에서 문제에서 요구하는 내용에 따하서 구현하는 내용이 다를 수 있음

- 이 문제에서는 값을 읽어서 result라는 ArrayList에 넣는 것이 요구사항

 

- while을 종료하기 위한 탐색 종료 시점을 확인해야 함 (모든 노드 탐색 완료, 목적지 도착 완료 등)

 

- 이동을 하는 방식도 문제마다 다를 수 있음

- 이 문제에서는 달팽이모양 방향을 요구하여서, Point클래스의 dist에 이동 방향에 대한 정보를 둠

- 이전에 사용한 방향으로 먼저 가보고, 아니면 다른 방향을 선택하도록 구현함