[구름톤 챌린지 12일차] 발전기

이번 문제는 dfs를 활용하여 문제를 풀었다. dfs를 구현하기 위해 stack을 활용할 수도 있고 재귀함수를 활용할 수도 있는데 이번 풀이는 스택을 활용해서 풀었다.

 

배운 점

그래프 탐색 알고리즘을 마지막으로 접한지 오래됐는데 이번 문제를 풀면서 다시금 상기하고 공부할 수 있어서 좋았다.

하나의 조건식에 2~3개 이상의 논리 연산자를 사용하는 것이 잘못되었다는걸 깨달았다. short-circuit evaluation에 대해서 다시금 상기할 수 있는 기회였고 앞으론 조건식의 논리연산자를 최대한 적게 쓰는 방향으로 풀어야 한다고 느꼈다.

 

어려웠던 점

자바로 알고리즘 문제를 풀이한 지 좀 됐는데 그럼에도 여전히 문법 오류를 여러번 겪게 되는거 같다. 한번에 통과하지 못하고 문법 오류를 수정해나가면서 완성해나가는데 앞으로 많은 문제를 풀면서 이런 부분이 해소되었으면 좋겠다.

 

느낀 점

이 분야를 공부하면서 알고리즘 문제도 적지 않게 푼거 같은데 여전히 어려운 부분이 많은거 같다. 그럼에도 발전한 부분이 있고 다양한 문제를 풀고 새로운 유형들을 접하다 보면 어제보다 나은 내가 될거라 믿고 꾸준히 문제를 풀어나가야겠다.

 

 

import java.util.*;
import java.io.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] board = new int[N][N];
		boolean[][] boolBoard = new boolean[N][N];
		
		for(int i = 0; i < N; i++){
			String[] temp = br.readLine().split(" ");
			for(int j = 0; j < N; j++){
				board[i][j] = Integer.parseInt(temp[j]);
			}
		}
		int[] dy = {-1, 0, 1, 0};
		int[] dx = {0, 1, 0, -1};
		int count = 0;
		
		LinkedList<Integer[]> stack = new LinkedList<>();
		for(int i = 0; i < N; i++){		
			for(int j = 0; j < N; j++){
				if(board[i][j] == 1 && boolBoard[i][j] == false){
					Integer[] tempYX = {i, j};
					stack.addLast(tempYX);
					while(!stack.isEmpty()){
						Integer[] tempYX2 = stack.removeLast();
						boolBoard[tempYX2[0]][tempYX2[1]] = true;
						for(int m = 0; m < 4; m++){
							int yy = dy[m] + tempYX2[0];
							int xx = dx[m] + tempYX2[1];
							if(yy < 0 || yy >= N || xx < 0 || xx >= N || boolBoard[yy][xx] == true || board[yy][xx] == 0)
								continue;
							else{
								Integer[] tempYX3 = {yy, xx};
								stack.addLast(tempYX3);
							}							
						}						
					}
					count += 1;
				}
			}
		}
		
		System.out.println(count);
	}
}