[프로그래머스(Programmers)][자바(java)] (Lv3) 11주차 - 아이템 줍기 <위클리 챌린지>

 

https://programmers.co.kr/learn/courses/30/lessons/87694

코딩테스트 연습 - 11주차

 

문제 풀이

 

import java.util.*;

public class Solution {
	
	class Position {
		int x, y, m;
		public Position(int x, int y, int m) {
			this.x = x;
			this.y = y;
			this.m = m;
		}
	}

	public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
		int xs, ys, xe, ye, x_max, y_max; x_max = y_max = 0;
		int n = rectangle.length, r[], i, j, k;
		for (i = 0; i < n; ++i) {
			r = rectangle[i];
			for (j = 0; j < 4; ++j) r[j] *= 2;
			xe = r[2]; ye = r[3];
			x_max = x_max < xe ? xe : x_max;
			y_max = y_max < ye ? ye : y_max;
		}
		int w = y_max + 1, h = x_max + 1;
		boolean t[][] = new boolean[h][w];
		for (i = 0; i < n; ++i) {
			r = rectangle[i];
			xs = r[0]; ys = r[1]; xe = r[2]; ye = r[3];
			for (j = xs + 1; j < xe; ++j)
				for (k = ys + 1; k < ye; ++k)
					t[j][k] = true;
		}
		boolean b[][] = new boolean[h][w];
		for (i = 0; i < n; ++i) {
			r = rectangle[i];
			xs = r[0]; ys = r[1]; xe = r[2]; ye = r[3];
			for (j = ys; j <= ye; ++j) {
				if (!t[xs][j]) b[xs][j] = true;
				if (!t[xe][j]) b[xe][j] = true;
			}
			for (j = xs; j <= xe; ++j) {
				if (!t[j][ys]) b[j][ys] = true;
				if (!t[j][ye]) b[j][ye] = true;
			}
		}
		int xc = characterX * 2, yc = characterY * 2, xi = itemX * 2, yi = itemY * 2;
		int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}, d, x, y, m, nx, ny, nm;
		Queue<Position> q = new ArrayDeque<>(); Position p;
		boolean v[][] = new boolean[h][w];
		q.add(new Position(xc, yc, 0));
		v[xc][yc] = true;
		while (!q.isEmpty()) {
			p = q.remove();
			x = p.x; y = p.y; m = p.m;
			for (d = 0; d < 4; ++d) {
				nx = x + dx[d]; ny = y + dy[d];
				if (nx < 0 || nx >= h || ny < 0 || ny >= w || !b[nx][ny] || v[nx][ny])
					continue;
				nm = m + 1;
				if (nx == xi && ny == yi) return nm / 2;
				q.add(new Position(nx, ny, nm));
				v[nx][ny] = true;
				
			}
		}
		return 0;
	}
}

 

예제 1를 대표로 설명

 

• 입력받은 int[][] rectangle 배열을 순회하며 각 좌표값을 2배로 늘림
  ( 좌표나 배열에서 한 정사각형을 기준으로,
    좌표는 정사각형의 모서리(교점) 한 점을 기준으로 보는 것이고 배열은 정사각형 그 자체이므로
    배열에서 정사각형 한 칸을 좌표의 한 점으로 취급 )

 

• boolean t[][] 생성하여 한 직사각형의 테두리를 제외한 부분에 true 값을 대입

 

• boolean b[][] 생성하여 한 직사각형의 테두리에만 true 값을 대입하되,
  그 위치( x, y )가 직사각형의 안에 있는 경우( t[x][y] == true )는 제외

 

• 캐릭터가 위치한 좌표( int xc, yc ), 아이템이 위치한 좌표( int xi, yi ) 역시 x, y 좌표값을 각각 두 배로 늘림

 

• 캐릭터가 위치한 좌표를 시작점으로 하여, BFS 하면서 이동 횟수를 세다가 아이템이 위치한 좌표에 도착하면 종료 후 횟수/2 한 값을 리턴