/ BOJ

BOJ_10157_자리배정_JAVA

문제 : 자리배정

링크 : BOJ_10157_자리배정

접근 방식

10157_1

위 그림처럼 수를 집어넣는데, 배열을 사용하기 어렵게 그림을 꼬아놓았다. 위 그림을 90도 돌려서, 행을 R로, 열을 C로 생각하고 풀면 된다.

며칠 전 풀었던 SWEA의 달팽이수열 문제와 방향성이 같아서 푸는데는 크게 어려움이 없었다.

단위벡터 배열을 생성하여 방향을 결정짓고 해당 방향으로 이동하면서 값을 집어넣다가, 벽을 만나거나 값이 이미 들어있는 상태라면 방향을 바꿔주도록 하면 배열은 위 그림처럼 값이 들어가게 된다. 따라서 위 알고리즘대로 값을 집어넣다가 찾아야되는 수가 나타나면 해당 좌표값을 출력한다.

풀이 방법

  1. 단위벡터 배열 dir을 선언한다.

  2. R*C 크기의 배열을 선언한다. 세로줄을 C로, 가로줄을 R으로 한다.

  3. 첫 번쨰 값에 1을 할당하고 반복문을 돌린다.

  4. 배열의 크기보다도 주어진 값이 더 크다면 바로 0을 출력하고 프로그램을 종료한다.

  5. 만약 주어진 값이 1이라면 1 1 을 출력하고 프로그램을 종료한다.

  6. 두 경우가 아닐 경우 반복을 하는데, dir의 벡터값대로 진행하며 배열에 cnt 값을 증가시키며 하나씩 집어넣는다.

  7. 벽을 만나거나 값이 0이 아닐 경우 단위벡터 배열의 값을 1 증가시켜 방향을 바꿔준다.

  8. cnt가 주어진 값과 같아졌을 때 해당 좌표를 출력하고 프로그램을 종료한다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_10157_자리배정 {

	public static void main(String[] args) throws IOException {


		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int[][] dir = { {0,1},{1,0},{0,-1},{-1,0} };
				//		좌	     하		  우		 상
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		int C  = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());

		int K = Integer.parseInt(in.readLine());
		int[][] arr = new int[C+1][R+1];
		int cnt = 1;
		int dirr = 0;
		int x = 1;
		int y = 1;
		arr[x][y] = cnt;

		if(C*R < K) {
			System.out.println(0);
			return;
		}
		if(K == 1) {
			System.out.println(1+" "+1);
			return;
		}

		while(cnt < C*R) {

			int dx = x + dir[dirr][0];
			int dy = y + dir[dirr][1];
			if(dx > 0 && dx <= C && dy > 0 && dy <= R && arr[dx][dy] == 0) {
				arr[dx][dy] = ++cnt;
				x = dx;
				y = dy;
			}else {
				dirr = (dirr+1)%4;
			}

			if(cnt == K) {
				System.out.println(dx + " " + dy);
				break;
			}
		}


	}

}