mingssssss

1. 문제

https://www.acmicpc.net/problem/13565

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    
    // 전역 변수 설정
	static ArrayList<ArrayList<Character>> list;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		list = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			char[] c = st.nextToken().toCharArray();
			for (int j = 0; j < M; j++) {
				list.get(i).add(c[j]);
			}
		}
		// 입력 종료

		for (int j = 0; j < M; j++) {
			if (list.get(0).get(j) == '0') {
				bfs(0, j, N, M, list);
			}
		}

        // 마지막 째 줄에 2가 있다면 침투가 가능한 경우이므로
		for (int i = 0; i < M; i++) {
			if (list.get(N - 1).get(i) == '2') {
				System.out.println("YES");
				return;
			}
		}
        // return이 안 됐다면 침투가 불가능한 경우이므로
		System.out.println("NO");
        
//      출력
//		for (int i = 0; i < N; i++) {
//			for (int j = 0; j < M; j++) {
//				System.out.printf("%s ", list.get(i).get(j));
//			}
//			System.out.println();
//		}


	}

	private static void bfs(int r, int c, int N, int M, ArrayList<ArrayList<Character>> list) {

		Queue<int[]> q = new LinkedList<>();

		q.add(new int[] { r, c });

		while (!q.isEmpty()) {

			int[] now = q.poll();

			for (int i = 0; i < 4; i++) {

				int nextX = now[0] + dx[i];
				int nextY = now[1] + dy[i];

				if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
					continue;
				}

				if (list.get(nextX).get(nextY) != '0') {
					continue;
				}

				list.get(nextX).set(nextY, '2');
				q.add(new int[] { nextX, nextY });

			}
		}

	}

}

3. 리뷰

리스트의 최하단에서 최상단까지 연결되어있는지 확인하는 문제이다

어차피 행렬로 접근할 것이므로 위에서부터 탐색해서 맨 아래까지 연결되어 있는지

확인해도 문제 없었다.

ArrayList로 입력값을 받아서 리스트를 구성하고

방문배열을 만들 필요 없이 탐색한 자리를 2로 바꾸어 주었다.

bfs를 다 돌고 가장 아래에 있는 행의 열들을 탐색해서

하나라도 2가 있다면 연결되어 있다는 뜻이므로, 답을 구했다.

제출 후 다른 분들의 코드를 보니 BufferWriter을 많이들 쓰셨다.

또 입력을 그대로 받고 아스키코드를 이용하여 푸신 분들도 있었다.

앞으로 시간이나 메모리 측면에서 더 개선해야 할 부분인 것 같다.