문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

코드 (Java)

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

class Solution
{
	private static int N, M, R, C, L;
	private static int[][] map;
	private static boolean[][] visited;
	private static final int ROW = 0, COL = 1, TIME = 2;
	
	public static void main(String args[]) throws Exception
	{
//		System.setIn(new FileInputStream("res/input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T;
		T = Integer.parseInt(br.readLine().trim());

		for(int test_case = 1; test_case <= T; test_case++)
		{
			StringTokenizer st = new StringTokenizer(br.readLine().trim());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			
			map = new int[N][M];
			visited = new boolean[N][M];
			
			for (int row = 0; row < N; ++row) {
				st = new StringTokenizer(br.readLine().trim());
				for (int col = 0; col < M; ++col) {
					map[row][col] = Integer.parseInt(st.nextToken());
				}
			}
			
			//it's just...bfs.
			int possibleCnt = 0;
			Queue<int[]> q = new LinkedList<>();
			
			q.add(new int[] {R, C, 1});
			visited[R][C] = true;
			
			while (!q.isEmpty()) {
				int[] curNode = q.poll();
				possibleCnt++;
				if (curNode[TIME] == L) continue;
				
				int type = map[curNode[ROW]][curNode[COL]];
				
				//right
				if (type == 1 || type == 3 || type == 4 || type == 5) {
					int newR =  curNode[ROW];
					int newC = curNode[COL] + 1;
					if (newC >= 0 && newC < M && !visited[newR][newC]) {
						int newType = map[newR][newC];
						if (newType == 1 || newType == 3 || newType == 6 || newType == 7) {
							visited[newR][newC] = true;
							q.add(new int[] {newR, newC, curNode[TIME] + 1});
						}
					}
				}
				
				//left
				if (type == 1 || type == 3 || type == 6 || type == 7) {
					int newR =  curNode[ROW];
					int newC = curNode[COL] - 1;
					if (newC >= 0 && newC < M && !visited[newR][newC]) {
						int newType = map[newR][newC];
						if (newType == 1 || newType == 3 || newType == 4 || newType == 5) {
							visited[newR][newC] = true;
							q.add(new int[] {newR, newC, curNode[TIME] + 1});
						}
					}
				}
				
				//up
				if (type == 1 || type == 2 || type == 4 || type == 7) {
					int newR =  curNode[ROW] - 1;
					int newC = curNode[COL];
					if (newR >= 0 && newR < N && !visited[newR][newC]) {
						int newType = map[newR][newC];
						if (newType == 1 || newType == 2 || newType == 5 || newType == 6) {
							visited[newR][newC] = true;
							q.add(new int[] {newR, newC, curNode[TIME] + 1});
						}
					}
				}
				
				//down
				if (type == 1 || type == 2 || type == 5 || type == 6) {
					int newR =  curNode[ROW] + 1;
					int newC = curNode[COL];
					if (newR >= 0 && newR < N && !visited[newR][newC]) {
						int newType = map[newR][newC];
						if (newType == 1 || newType == 2 || newType == 4 || newType == 7) {
							visited[newR][newC] = true;
							q.add(new int[] {newR, newC, curNode[TIME] + 1});
						}
					}
				}
			}
			bw.write("#" + test_case + " " + possibleCnt + "\n");
		}
		bw.flush();
		bw.close();
	}
}

풀이

• 조금 복잡한 그래프 탐색. 딱 그정도라 흥미로운 문제는 아니었다.

• BFS로 풀었으나 DFS로도 가능하다. 다만 문제 조건이 BFS에 최적화되어 있어서...