BOJ 10157 자리배정

문제 분석

- 하/우/상/좌 방향으로 반복하여 숫자를 찾는다.

- 위의 방향으로 한 바퀴를 돌면 끝 값을 -1해주면서 갈 수 있는 최대 숫자까지 접근한다.

 

 

문제 풀이

1) dr/dc 배열을 통해 하/우/상/좌 방향으로 이동할 수 있도록 값을 담는다.

2) 최대값까지 갈 수 있도록 4방향을 반복한다.

3) 원하는 값에 도달하면 해당 좌표 위치를 출력한다. 

cf) 방문 여부를 판단하여 방문하였을 경우 길이를 줄인다. (길이는 R과 C로 판단하고, 한 바퀴를 돌고 안 쪽 사각형으로 들어갈 경우 visited를 활용하여 다 돌았는지 확인한다.)

★ 출력 형식에 주의해야한다. ★
배열로 받아서
0,0 / 0,1 / 0,2 / 0,3 / 0,4 / 0,5 / 0,6
1,0 / 1,1 / 1,2 / 1,3 / 1,4 / 1,5 / 1,6
2,0 / 2,1 / 2,2 / 2,3 / 2,4 / 2,5 / 2,6
3,0 / 3,1 / 3,2 / 3,3 / 3,4 / 3,5 / 3,6
4,0 / 4,1 / 4,2 / 4,3 / 4,4 / 4,5 / 4,6
5,0 / 5,1 / 5,2 / 5,3 / 5,4 / 5,5 / 5,6
로 저장되면서 하우상좌방향으로 움직이는데  42의 경우 r c로 출력하게되면 3, 4(r+1, c+1)로 출력된다.

그러나 프로그램에서 원하는 출력 형식은 4,3이다.
즉, c와 r이 같은 대각선을 기준으로 대칭되어 출력해야한다.

배열의 c와 r값으로 출력해야 올바른 출력형식대로 출력된다.

 

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

public class Main {
	private static int[][] map;
	private static boolean[][] visited;
	private static int[] dr = { 1, 0, -1, 0 };
	private static int[] dc = { 0, 1, 0, -1 };

	private static int C, R, K, nr, nc, r, c, goal;

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

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

		C = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(br.readLine());
		map = new int[R][C];
		visited = new boolean[R][C];

		// 다 돌고도 못찾았을 때 최종 끝점
		goal = R * C;

		// 초기값 설정
		map[0][0] = 1;
		visited[0][0] = true;
		
		if (K > goal) {// 구하는 자리가 좌표의 최대값보다 크면 바로 0출력
			System.out.println(0);
		} else {
			chk(1, R, C);
		}
	}// main

	private static void chk(int start, int R, int C) {
	
		for (int k = 0; k < 4; k++) {
			while (true) {
				if (start == K) {
					System.out.println((c + 1) + " " + (r + 1));
					System.exit(0);
				}

				nr = r + dr[k];
				nc = c + dc[k];

				if (nr < 0 || nr >= R || nc >= C || nc < 0)
					break;

				if (!visited[nr][nc]) {
					map[nr][nc] = ++start;
					visited[nr][nc] = true;

					r = nr;
					c = nc;
				} else {
					break;
				}
			}
		}

		chk(start, R - 1, C - 1);

	}// chk
}// class-end