[Programmers 위클리 챌린지 11주차] 아이템 줍기

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/87694

코딩테스트 연습 - 11주차

재미있는 구현 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 모든 직사각형의 테두리를 우선 방문 완료 표시해줍니다.

2. 모든 직사각형의 내부를 방문 제외해줍니다.

3. 1번과 2번을 완성하면 테두리가 완성이 되는데 (x, y), (x + 1, y) 좌표가 테두리로 설정이 되어 방문 완료 표시가 되지만 (x, y) -> (x + 1, y)로 가는 경로는 없고 (x, y) -> (x, y + 1) -> (x + 1, y + 1) -> (x + 1, y)로 가는 경로가 있는 케이스가 있습니다.

3.1 BFS를 적용할 경우 위와 같은 케이스를 판별하기 힘드므로 1번과 2번을 표시할 때 각각의 변을 두배로 늘린 뒤 표시를 해준다면 3번과 같은 케이스를 방지할 수 있습니다. 따라서, 1번과 2번 과정을 변의 길이를 두 배씩 늘린 상태로 진행합니다. (즉, 좌표를 두배씩)

4. 시작점부터 끝점까지 BFS를 진행하며 가장 빨리 도착한 경로의 길이를 반환해줍니다.

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <queue>
	using namespace std;
	const int MAX = 100 + 10;
	typedef struct
	{
	int y, x, cnt;
	} Status;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	bool parameter[MAX][MAX][4]; // y, x, dir
	bool visited[MAX][MAX];
	int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
	// 각 직사각형 테두리
	for (auto r : rectangle)
	{
	// 가로
	for (int x = r[0] * 2; x <= r[2] * 2; x++)
	{
	parameter[r[1] * 2][x][2] = true;
	parameter[r[3] * 2][x][2] = true;
	parameter[r[1] * 2][x][3] = true;
	parameter[r[3] * 2][x][3] = true;
	}
	// 세로
	for (int y = r[1] * 2; y <= r[3] * 2; y++)
	{
	parameter[y][r[0] * 2][0] = true;
	parameter[y][r[2] * 2][0] = true;
	parameter[y][r[0] * 2][1] = true;
	parameter[y][r[2] * 2][1] = true;
	}
	}
	// 각 직사각형 내부 visited 해제
	for (auto r: rectangle)
	{
	for (int y = r[1] * 2 + 1; y < r[3] * 2; y++)
	{
	for (int x = r[0] * 2 + 1; x < r[2] * 2; x++)
	{
	for (int k = 0; k < 4; k++)
	{
	parameter[y][x][k] = false;
	}
	}
	}
	}
	queue<Status> q;
	q.push({characterY * 2, characterX * 2, 0});
	visited[characterY * 2][characterX * 2] = true;
	while(!q.empty())
	{
	int curY = q.front().y;
	int curX = q.front().x;
	int cnt = q.front().cnt;
	q.pop();
	if (curY == itemY * 2 && curX == itemX * 2)
	{
	return cnt / 2;
	}
	for (int k = 0; k < 4; k++)
	{
	int nextY = curY + moveDir[k].y;
	int nextX = curX + moveDir[k].x;
	if (nextY < 2 || nextY > 100 || nextX < 2 || nextX > 100)
	{
	continue;
	}
	if (!parameter[nextY][nextX][k] || visited[nextY][nextX])
	{
	continue;
	}
	visited[nextY][nextX] = true;
	q.push({nextY, nextX, cnt + 1});
	}
	}
	return -1;
	}

view raw .cpp hosted with ❤ by GitHub

 

 

개발환경: 프로그래머스

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~