[SWEA] 1861. 정사각형 방

new Dean( );·2021년 8월 6일
0

알고리즘

목록 보기
19/30

문제

1861. 정사각형 방
N*N 배열에 1~N^2 사이의 수가 중복되지 않게 적혀있다. (방 번호)
방번호+1 인 상하좌우로 인접한 방으로만 이동이 가능하다. 이때, 어느 방에서 출발하면 가장 많이 이동할 수 있는지 찾고, 방번호와 이동한 방 개수를 출력하라.

풀이

문제에서 주어진 대로 구현한다.

  1. 이중for문으로 모든 지점에서 시작한다.
  2. BFS로 상하좌우 방 중에 현재방보다 1만큼 큰 방으로 이동한다.
    • (r,c)를 (nr, nc)로 갱신한다. queue가 필요없다. 이동할 수 있는 곳이 한 군데니까!!
    • cnt++ (방 몇 개 돌았는지)
  3. 최대값을 찾아서 출력한다.

자바코드

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{	
	static int [] dr = {-1, 0, 1, 0};
	static int [] dc = {0, -1, 0, 1};
	
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt(); 
		int n;
		for(int test_case = 1; test_case <= T; test_case++)
		{				
			n = sc.nextInt();
			
			int [][] map = new int[n][n];
			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++) {
					// Load map
					map[i][j] = sc.nextInt();
				}
			}
			
			int max = -1;
			int roomNumber = 10000; // 가장 많이 이동할 수 있는 방의 번호 
			int temp;
			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++) {
					temp = BFS(i, j, map, n);
					if (temp > max) {
						max = temp;
						roomNumber = map[i][j];
					} else if (temp == max && map[i][j]<roomNumber) {
						max = temp;
						roomNumber = map[i][j];
					}
				}
			}
 			
			System.out.printf("#%d %d %d\n", test_case, roomNumber, max);
		}
	}
	
	static int BFS(int r, int c, int [][] map, int n) {
		int cnt=1;
		
		int nr, nc;
		boolean isPromising = false;
		while(true) {
			isPromising = false;
			for (int d=0; d<4; d++) {
				nr = r+dr[d];
				nc = c+dc[d];
				
				if(nr<0||nr>=n||nc<0||nc>=n) continue;

				if (map[nr][nc]-map[r][c] == 1) {
					cnt++;
					r = nr;
					c = nc;
					isPromising = true;
					break;
				}
			}
			if (!isPromising) break;
		}
		
		
		return cnt;
	}

}

까다로웠던

if (temp > max) {
	max = temp;
	roomNumber = map[i][j];
} else if (temp == max && map[i][j]<roomNumber) {
	max = temp;
	roomNumber = map[i][j];
}

이 부분 코드가 완벽하게 겹치는데, 하나로 합치지 못했다. 조건에 ||로 둘 다 넣으면 되겠지만 조건이 너무 길어지는건 싫음ㅎㅎ

0개의 댓글