[Softeer] 장애물 인식 프로그램 (Java)

[Softeer] 장애물 인식 프로그램 (Java)

문제

https://softeer.ai/practice/info.do?idx=1&eid=409&sw_prbl_sbms_sn=232380

풀이/후기

하... BFS 문제인거 바로 파악해서 자신있게 풀기 시작했는데

정말 한참 부족하다는 것을 느꼈다...

 

일단 visited를 구현할 때 int로 할지, boolean으로 할지 감을 못잡겠다.

BFS문제에서 어떤 값을 원하냐에 따라 달라지는 것 같은데

이전에 visited외에 별도로 카운트 세다가 고생한 이후로 visited에 +1을 해서 카운트하는 방식을 선호하게 되었는데,

이번엔 또 boolean으로 풀고 별도로 카운트를 하는 방식으로 완성했다.

아무래도 이코드 저코드 참고하고 그 디테일까지 파악하지 못하니 이런 판단도 안되는 것 같다. 하......

 

그리고 두번째로 항상 nextX, nextY를 범위 내에서 구현하는 것을 선호해왔는데,

이렇게 푸니 자꾸 테스트케이스 하나에서 런타임 에러가 발생했다.

도대체 이유를 모르겠어서 nextX, nextY를 범위 외로 구현하는 코드를 넣어보니 바로 정답 결과가 나왔다.

아예 버릇을 이렇게 들여야지 이런 사소한 점들 때문에 시간고생 정신고생 별고생을 다한다.

 

코드

package Softeer;

import java.util.*;
import java.io.*;

public class lv2_3 {
	// 장애물 인식 프로그램
	static int N;
	static int[][] map;
	static boolean[][] visited;

	static LinkedList<Integer> list = new LinkedList<>();
	static int cnt = 0;

	static int[][] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	static Queue<int[]> q = new LinkedList<>();

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visited = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			String[] inp = br.readLine().split("");
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(inp[j]);
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					// 장애물이 있고 방문하지 않은 경우
					cnt++;
					bfsFn(i, j);
				}

			}

		}

		sb.append(cnt).append("\n");
		Collections.sort(list);
		for (int size : list)
			sb.append(size).append("\n");
		System.out.println(sb);

	}

	static void bfsFn(int x, int y) {
		q.add(new int[] { x, y });
		visited[x][y] = true;

		int tempCnt = 1;
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int curX = cur[0];
			int curY = cur[1];

			for (int i = 0; i < 4; i++) {
				int nextX = curX + dir[i][0];
				int nextY = curY + dir[i][1];

				if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N || map[nextX][nextY] == 0 || visited[nextX][nextY]) {
					continue;
				} else {
					q.add(new int[] { nextX, nextY });
					visited[nextX][nextY] = true;
					tempCnt++;
				}

			}
		}

		list.add(tempCnt);

	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/c981099a3b910c220ec4ec8d55565a82289f59ec

참고

https://void2017.tistory.com/362