300x250
300x250

뱀파이어 서바이벌 같은 대규모 오브젝트들을 다루는 게임을 만들었었는데 이게임이 후반부로 갈수록 발열과 버벅거림 같은 렉 현상이 발견이 되더라고요. 처음엔 dots를 적용해야 하나 싶었는데 이 프로젝트를 유니티 2021.3.5f1로 진행을 해서

 

1.0.0 pre 버전은 유니티 2022.2.0b8 버전부터 지원을 하더라고요 어쩔 수 없이 유니티 프로파일러를 돌려서 최대한 문제점을 찾아보려고 했어요.

확인을 해보니 예상대로 대규모의 적 오브젝트들이 리소스를 가장 많이 사용하는 것 을 확인 하였고 CoroutineDelayedCalls안에 이동관련해서 리소스를 가장 많이 잡아먹고 있었기에 고민을 해봤어요.

Enemy.cs

적오브젝트 스크립트인데 각 오브젝트마다 생성이 되면 MoveRoutine 코루틴을 오브젝트가 죽을 때까지 실행하게 되는 코드로 작성이 돼있어요. 즉 Enemy객체가 200개라면 코루틴 200개가 돌고 있는 거죠.

 

그래서 실험을 한번 해보기로 했어요. 처음 아이디어는 Enemy들이 각자가 코루틴을 돌리며 이동하는 게 아니라 Enemy들을 모두 관리하는 EnemySpawner라는 객체가 있는데 이 객체가 Enemy들 안에 있는 Move 메서드를 호출하게 하는 코루틴을 한 개만 호출하게 하는 방식이에요.

 

이게 과연 더 효율적인 것일까를 검증하기 위해서 프로젝트를 하나 새로 만들어서 테스트를 해봤어요.

결론부터 말하자면 더 효율적이지 않았어요. 실패입니다.

아래내용은 실패에 관한 내용이에요.

 

간단하게 움직이는 플레이어를 만들고

 

실험을 도와줄 UnityChan들이에요.

 

플레이어를 열심히 따라와 줘야 해요.

 

먼저 500 마리 정도 만들어서 기존 이동코드를 사용해 봤어요.

 

EnemySpawner.cs

using System.Collections;
using UnityEngine;

public class EnemySpawner : MonoBehaviour
{
    public GameObject[] enemyGos;
    public GameObject rangeObject;
    public GameObject playerGo;
    private BoxCollider rangeCollider;

    public void Init(int spawnAmount)
    {
        rangeCollider = rangeObject.GetComponent<BoxCollider>();
        this.SpawnEnemys(spawnAmount);
    }

    private void SpawnEnemys(int spawnAmount)
    {
        StartCoroutine(this.SpawnEnemysImpl(spawnAmount));
    }

    private IEnumerator SpawnEnemysImpl(int spawnAmount)
    {
        for (int i = 0; i < spawnAmount; i++)
        {
            var randEnemyIndex = Random.Range(0, enemyGos.Length);
            // 생성 위치 부분에 위에서 만든 함수 Return_RandomPosition() 함수 대입
            GameObject enemyGo = Instantiate(enemyGos[randEnemyIndex], Return_RandomPosition(), Quaternion.identity, this.transform);
            Enemy enemy = enemyGo.GetComponent<Enemy>();
            enemy.Init(playerGo);
            yield return new WaitForSeconds(0.1f);
        }
    }


    private Vector3 Return_RandomPosition()
    {
        Vector3 originPosition = rangeObject.transform.position;
        
        // 콜라이더의 사이즈를 가져오는 bound.size 사용
        float range_X = rangeCollider.bounds.size.x;
        float range_Z = rangeCollider.bounds.size.z;

        range_X = Random.Range((range_X / 2) * -1, range_X / 2);
        range_Z = Random.Range((range_Z / 2) * -1, range_Z / 2);


        Vector3 RandomPostion = new Vector3(range_X, 0f, range_Z);

        Vector3 respawnPosition = originPosition + RandomPostion;
        return respawnPosition;
    }
}

 

Enemy.cs

using System.Collections;
using UnityEngine;

public class Enemy : MonoBehaviour
{
    private float moveSpeed = 3f;
    private GameObject playerGo;
    public void Init(GameObject playerGo)
    {
        this.playerGo = playerGo;
        this.Move();
    }
    private void Move()
    {
        StartCoroutine(this.MoveRoutine());
    }

    private IEnumerator MoveRoutine()
    {
        while (true)
        {
            this.transform.LookAt(this.playerGo.transform.position);

            transform.Translate(Vector3.forward * Time.deltaTime * this.moveSpeed);

            yield return null;
        }
    }
}

 

 

 

이렇게 했을 때 프로파일러를 확인해 보면

 

500개에 Calls가 있고 1.17 Time ms값을 갖고 있어요.

코루틴이 500개가 돌고 있다는 거죠.

 

이걸 이제 EnemySpawner에서 전부 관리하게 해 볼게요.

 

EnemySpawner.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class EnemySpawner : MonoBehaviour
{
    public GameObject[] enemyGos;
    public GameObject rangeObject;
    public GameObject playerGo;
    private BoxCollider rangeCollider;

    private List<Enemy> enemyList;

    public void Init(int spawnAmount)
    {
        rangeCollider = rangeObject.GetComponent<BoxCollider>();
        this.enemyList = new List<Enemy>();

        StartCoroutine(this.SpawnEnemys(spawnAmount));
        StartCoroutine(this.MoveEnemys());
    }

    private IEnumerator SpawnEnemys(int spawnAmount)
    {
        for (int i = 0; i < spawnAmount; i++)
        {
            var randEnemyIndex = Random.Range(0, enemyGos.Length);
            // 생성 위치 부분에 위에서 만든 함수 Return_RandomPosition() 함수 대입
            GameObject enemyGo = Instantiate(enemyGos[randEnemyIndex], Return_RandomPosition(), Quaternion.identity, this.transform);
            Enemy enemy = enemyGo.GetComponent<Enemy>();
            enemy.Init(playerGo);

            this.enemyList.Add(enemy);
            yield return new WaitForSeconds(0.1f);
        }
        Debug.Log("Spawn Complete");
    }


    private Vector3 Return_RandomPosition()
    {
        Vector3 originPosition = rangeObject.transform.position;
        
        // 콜라이더의 사이즈를 가져오는 bound.size 사용
        float range_X = rangeCollider.bounds.size.x;
        float range_Z = rangeCollider.bounds.size.z;

        range_X = Random.Range((range_X / 2) * -1, range_X / 2);
        range_Z = Random.Range((range_Z / 2) * -1, range_Z / 2);


        Vector3 RandomPostion = new Vector3(range_X, 0f, range_Z);

        Vector3 respawnPosition = originPosition + RandomPostion;
        return respawnPosition;
    }

    private IEnumerator MoveEnemys()
    {
        while(true)
        {
            foreach (var enemy in enemyList)
            {
                enemy.Move();
            }
            yield return null;
        }
    }
}

 

Enemy.cs

using System.Collections;
using UnityEngine;

public class Enemy : MonoBehaviour
{
    private float moveSpeed = 3f;
    private GameObject playerGo;
    public void Init(GameObject playerGo)
    {
        this.playerGo = playerGo;
        this.Move();
    }
    public void Move()
    {
        this.transform.LookAt(this.playerGo.transform.position);

        transform.Translate(Vector3.forward * Time.deltaTime * this.moveSpeed);

        //StartCoroutine(this.MoveRoutine());
    }

    private IEnumerator MoveRoutine()
    {
        while (true)
        {
            this.transform.LookAt(this.playerGo.transform.position);

            transform.Translate(Vector3.forward * Time.deltaTime * this.moveSpeed);

            yield return null;
        }
    }
}

 

 

개인적으로 놀랐던 거는 500개의 코루틴이 돌아가는 거랑 똑같은 움직임으로 보였어요 전 이거까지만 확인했을 땐 최적화과 됐겠다 싶어서 프로파일러를 확인해 봤어요.

아~ 전혀 나아지지 않은 모습 실패예요. 

Calls는 1개로 줄어들었지만 TIme.ms가 전혀 줄어들지 않았어요.

 

아 될 거 같았는데 이게 안되네요.

300x250
300x250

게임을 만들다 보면 퍼즈상태를 구현 하기 위해서 Time.timeScale = 0 을 사용해서 손쉽게 구현 할 수 있어요.

 

 

 

using System.Collections;
using UnityEngine;
using UnityEngine.UI;

public class JeongTest2Main : MonoBehaviour
{
    public Text textTime;
    public Button btnPause;
    private float currentTime = 0;
    void Start()
    {        
        this.btnPause.onClick.AddListener(() =>
        {
            Time.timeScale = 0;
        });

        StartCoroutine(this.TimerRoutine());
    }

    private IEnumerator TimerRoutine()
    {
        while (true)
        {
            currentTime += Time.deltaTime;
            textTime.text = currentTime.ToString();
            yield return null;
        }        
    }
}

 

근데 이렇게 하면 게임 내에 있는 모든 시간이 멈춰 버려서 예를 들면 5초만 멈추기 같은 기능을 Time.deltaTime으론 구하기 힘들어져요. 그래서 유니티에서 제공하는게 아닌 C#에서 지원하는 System.Timers를 사용해서 구현하면 쉽게 할 수 있어요.

 

using System.Collections;
using System.Timers;
using UnityEngine;
using UnityEngine.UI;

public class JeongTest2Main : MonoBehaviour
{
    public Text textTime;
    public Button btnPause;
    private Timer timer;
    private float delta = 0;
    private float currentTime = 0;
    void Start()
    {        
        this.btnPause.onClick.AddListener(() =>
        {
            MyTimer();
            Time.timeScale = 0;
        });

        StartCoroutine(this.TimerRoutine());
    }

    private void MyTimer()
    {
        timer = new Timer();
        timer.Start();
        // 밀리세컨드 단위 1000 = 1초
        timer.Interval = 1000;

        timer.Elapsed += new System.Timers.ElapsedEventHandler(timer_Elapsed);  //주기마다 실행되는 이벤트 등록
    }

    private IEnumerator TimerRoutine()
    {
        while (true)
        {
            currentTime += Time.deltaTime;
            textTime.text = currentTime.ToString();
            yield return null;

            if (delta >= 5)
            {
                delta = 0;
                Time.timeScale = 1;
                timer.Stop();
                timer.Dispose();
            }
        }        
    }

    delegate void TimerEventFiredDelegate();
    void timer_Elapsed(object sender, System.Timers.ElapsedEventArgs e)
    {
        // 1초에 1씩증가
        delta += 1;
    }
}
300x250
300x250

1. 제목

- 백준 18111 마인크래프트

- BOJ 18111 마인크래프트

문제 링크 : 18111번: 마인크래프트 (acmicpc.net)

 

18111번: 마인크래프트

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게

www.acmicpc.net


2. 풀이 과정

 

완전탐색으로 문제 해결을 했어요.

일단 먼저 최대 쌓을 수 있는 높이를 구한 다음 (최대높이 = 총 블룩개수 / (가로 * 세로)) 높이 0부터 최대 높이 까지 쌓아보며 작업시간을 구한 후 가장 낮은 작업시간을 가진 값을 구하는 식으로 구현했어요.


3. 코드

#include <iostream>

using namespace std;


int map[500][500];
int col, row, ownBlocks;
int totalBlockAmount, maxHeight;
int t = 99999999, height;

void Solution()
{
	// 최대 높이 구하기
	// 최대 높이 = 총블록갯수 / (가로 * 세로)
	maxHeight = totalBlockAmount / (col * row);

	for (int h = 0; h <= maxHeight; h++)
	{
		int currentTime = 0;

		for (int y = 0; y < col; y++)
		{
			for (int x = 0; x < row; x++)
			{
				// 현재 높이보다 크다면 땅을 판다.
				if (map[y][x] > h)				
					currentTime += ((map[y][x] - h) *2);				
				// 현재 높이보다 작다면 블록을 쌓는다.
				else if (map[y][x] < h)
					currentTime += (h - map[y][x]);				
			}
		}

		// 현재 작업시간이 최솟값 보다 작다면 갱신
		if (currentTime < t)
		{
			t = currentTime;
			height = h;
		}
		// 현재 작업시간이 최솟값과 같으면서 현재 높이가 더 높다면 갱신
		if (currentTime == t)
		{
			if (height < h)
				height = h;
		}
	}

	cout << t << " " << height;
}

void Input()
{
	cin >> col >> row >> ownBlocks;
	totalBlockAmount += ownBlocks;

	for (int y = 0; y < col; y++)
	{
		for (int x = 0; x < row; x++)
		{
			cin >> map[y][x];
			totalBlockAmount += map[y][x];
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	Input();
	Solution();

	return 0;
}
300x250

'<C++ 백준 BOJ> > 구현' 카테고리의 다른 글

[백준 BOJ14891] 톱니바퀴 (C++)  (0) 2022.12.27
[백준 BOJ14719] 빗물 (C++)  (0) 2022.12.25
[백준 BOJ2174] 로봇 시뮬레이션 (C++)  (2) 2022.12.25
[백준 BOJ16918] 봄버맨 (C++)  (2) 2022.12.24
[백준 BOJ3190] 뱀 (C++)  (0) 2022.12.24
300x250

1. 제목

- 백준 14891 톱니바퀴

- BOJ 14891 톱니바퀴

문제 링크 : 14891번: 톱니바퀴 (acmicpc.net)

 

14891번: 톱니바퀴

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴

www.acmicpc.net


2. 풀이 과정

기본적으로 문제에서 톱니의 상태를 12시 방향부터 순서대로 0 또는 1로 주고 있어요. 즉 8개의 숫자들은

위와 같은 01234567 구조를 가지고 있어요.

이거를  오른쪽으로 회전 시킨다면

70123456으로 표현이 가능해요. 마찬가지로 왼쪽으로 회전시키면

12345670이 될 거예요. 그래서 전 톱니의 상태를 문자열로 저장한 다음 회전을 처리해줄 때 

우측 회전은 gear[index] = gear[index][7] + gear[index].substr(0, 7); 

즉 8번째 상태를 맨 앞으로 보내고 나머지를 뒤에 붙였고

좌측 회전은 gear[index] = gear[index].substr(1, 7) + gear[index][0]; 

맨 앞에 값을 맨뒤에 붙이는 식으로 회전을 구현했어요. 그리고 톱니가 회전할 때 좌우를 검사해서 회전을 시켜야 하는데 코드를 보시면 이미 회전을 시킨 상태에서 비교를 하는 거라서

우측으로 회전했을 때는 인덱스가 1씩 증가를 했으니 각각 7번, 3번 인덱스를 비교해주고 좌측일 때는 이와는 반대로 1씩 감소했으니 5번, 1번 인덱스를 비교해서 회전을 시켜주고 있어요.

재귀로 돌리고 있는데 한번 돌아간 톱니는 더 이상 돌릴 필요가 없기 때문에 방문처리를 별도로 해줘서 한번 돌아간 톱니는 함수를 바로 종료하게 구현했어요.

 


3. 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

string gear[6];
bool visit[6];
vector<pair<int, int>> v;
// 회전 횟수
int K;

void Reset()
{
	for (int i = 1; i < 5; i++)
	{
		visit[i] = false;
	}
}

void Rotation(int index, int dir)
{
	// 1234 톱니가 아니라면 즉시 종료
	if (index < 1 || index > 4)
		return;
	// 이미 한번 돌아간 톱니라면 즉시 종료
	if (visit[index] == true)
		return;

	// 돌아간 톱니 방문 표시
	visit[index] = true;

	// 우측방향
	if (dir == 1)
	{
		gear[index] = gear[index][7] + gear[index].substr(0, 7);

		if(gear[index][7] != gear[index - 1][2])
			Rotation(index - 1, -dir);
		if (gear[index][3] != gear[index + 1][6])
			Rotation(index + 1, -dir);
	}		
	// 좌측 방향
	else
	{
		gear[index] = gear[index].substr(1, 7) + gear[index][0];

		if (gear[index][5] != gear[index - 1][2])
			Rotation(index - 1, -dir);
		if (gear[index][1] != gear[index + 1][6])
			Rotation(index + 1, -dir);
	}
}

void Solution()
{
	int result = 0;
	// 사용하지 않는 톱니
	gear[0] = "00000000";
	gear[5] = "00000000";

	for (int i = 0; i < K; i++)
	{
		int gearIndex = v[i].first;
		int dir = v[i].second;

		Rotation(gearIndex, dir);
		Reset();
	}

	// 최종 톱니바퀴들의 12시 방향 체크
	for (int i = 1; i < 5; i++)
	{
		if (gear[i][0] == '1')
		{
			result += pow(2, i - 1);
		}
	}
	cout << result << endl;
}

void Input()
{
	for (int i = 1; i < 5; i++)
	{
		cin >> gear[i];
	}

	cin >> K;
	for (int i = 0; i < K; i++)
	{
		int gearIndex;
		int dir;
		cin >> gearIndex;
		cin >> dir;
		v.push_back({gearIndex, dir });
	}
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	Input();
	Solution();

	return 0;
}
300x250
300x250

1. 제목

- 백준 14719 빗물

- BOJ 14719 빗물

문제 링크 : 14719번: 빗물 (acmicpc.net)

 

14719번: 빗물

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치

www.acmicpc.net


2. 풀이 과정

 

왼쪽 블록을 기준점으로 시작해서 오른쪽으로 탐색을 시작하는데 매번 높이를 비교하며 현재 기준점이 되는 블록보다 높거나 같은 블록을 발견하면 기준점 블록을 해당 블록으로 갱신을 해줘요.

또한 매번 기준점 블록을 갱신하기 전 기준점 블록과 현재 탐색 중인 블록의 사이에 빈 곳이 존재한다면 기준점과 현재 블록의 높이 중 낮은 높이까지 빗물을 표시해 주어서 문제에서 요구하는 고인 빗물을 구할 수 있었어요.

빗물 체크를 할 때 탐색을 매번 기준점 블록이 바뀌기 전까지 탐색했던 곳을 또 탐색하는 낭비가 있기는 한데…. 너무 쉽게 풀려고 한 느낌이 있는 거 같아요.


3. 코드

#include <iostream>
#include <vector>

using namespace std;

// 세로 가로
int H, W;
// 맵
int map[501][501];
// 높이 저장 백터
vector<int> v;
// 정답 변수
int result;

void Marking(int startX, int endX)
{
	int height;
	if (v[startX] < v[endX])
		height = v[startX];
	else
		height = v[endX];


	for (int x = startX; x < endX; x++)
	{
		for (int y = 0; y < height; y++)
		{
			if (map[y][x] == 0)
			{
				result++;
				map[y][x] = 2;
			}
		}
	}
}

void Solution()
{
	int selectX = 0;
	for (int x = 1; x < W; x++)
	{
		Marking(selectX, x);

		// 현재 선택된 높이보다 더 높거나 같은 높이를 발견 했다면
		if (v[selectX] <= v[x])
			selectX = x;
	}
	cout << result << endl;
}

void Input()
{
	cin >> H >> W;

	for (int x = 0; x < W; x++)
	{
		int height;
		cin >> height;
		v.push_back(height);
		for (int y = 0; y < height; y++)
		{
			map[y][x] = 1;
		}
	}
}

int main()
{
	Input();
	Solution();
	return 0;
}
300x250
300x250

1. 제목

- 백준 2174 로봇 시뮬레이션

- BOJ 2174 로봇 시뮬레이션

문제 링크 : 2174번: 로봇 시뮬레이션 (acmicpc.net)

 

2174번: 로봇 시뮬레이션

첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순

www.acmicpc.net


2. 풀이 과정

 

로봇이 여러 개가 있을 수 있고 이 로봇들에게 회전 또는 전진 명령을 내릴 수 있어요. 이때 이 로봇들에게 전진 명령을 내릴 때 맵밖을 벗어나는 것은 맵에 사이즈를 벗어나는지만 체크해주면 될 것이고 나머지는 다른 로봇과의 충돌인데 이걸 저는 맵에 int형 2차원 배열로 표현해서 0은 빈칸 나머지는 각 로봇에 index를 표시해 주는 방법을 사용하여서 현재 명령을 내리고 있는 로봇이 이동할 좌표에 0이 아닌 값이 있다면 해당 index 로봇과 충돌했다는 것으로 문제에서 요구하는 조건을 수행할 수 있었어요.


3. 코드

#include <iostream>
#include <vector>

#define X first
#define Y second
using namespace std;

struct Robot
{
	int x;
	int y;
	int dir;
};
struct Command
{
	int index;
	char type;
	int count;
};

Robot robots[101];
Command commands[101];
int map[101][101];

int w, h;
int N, M;

// 위 오른쪽 아래 왼쪽
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void Solution()
{
	for (int i = 0; i < M; i++)
	{
		// 회전, 전진명령 구분
		char commandType = commands[i].type;
		// 해당 명령을 몇번 수행할 것인지
		int count = commands[i].count;
		// 명령을 내릴 로봇 index
		int index = commands[i].index;
		for (int j = 0; j < count; j++)
		{
			if (commandType == 'L')
				robots[index].dir = (robots[index].dir + 3) % 4;
			else if (commandType == 'R')
				robots[index].dir = (robots[index].dir + 1) % 4;
			else if(commandType == 'F')
			{
				int nx = robots[index].x + dx[robots[index].dir];
				int ny = robots[index].y + dy[robots[index].dir];
				map[robots[index].x][robots[index].y] = 0;
				// 이동할 좌표가 맵을 벗어난다면
				if (nx == 0 || ny == 0 || nx > w || ny > h)
				{
					cout << "Robot " << index << " crashes into the wall";
					return;
				}
				// 이동할 좌표가 빈공간이 아니라면
				if (map[nx][ny] != 0)
				{
					cout << "Robot " << index << " crashes into robot " << map[nx][ny];
					return;
				}
				robots[index].x = nx;
				robots[index].y = ny;
				map[nx][ny] = index;
			}
		}
	}
	// 정상수행 완료
	cout << "OK" << endl;

}

void Input()
{
	cin >> w >> h;
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		int x, y, dir = 0;
		char cdir;
		cin >> x >> y >> cdir;
		if (cdir == 'N')
			dir = 0;
		else if (cdir == 'E')
			dir = 1;
		else if (cdir == 'S')
			dir = 2;
		else if (cdir == 'W')
			dir = 3;
		robots[i] = { x, y, dir };
		map[x][y] = i;
	}

	for (int i = 0; i < M; i++)
	{
		int index, count;
		char type;
		cin >> index >> type >> count;

		commands[i] = { index, type, count };
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	Input();
	Solution();

	return 0;
}
300x250

'<C++ 백준 BOJ> > 구현' 카테고리의 다른 글

[백준 BOJ18111] 마인크래프트 (C++)  (0) 2022.12.27
[백준 BOJ14891] 톱니바퀴 (C++)  (0) 2022.12.27
[백준 BOJ14719] 빗물 (C++)  (0) 2022.12.25
[백준 BOJ16918] 봄버맨 (C++)  (2) 2022.12.24
[백준 BOJ3190] 뱀 (C++)  (0) 2022.12.24
300x250

1. 제목

- 백준 16918 봄버맨

- BOJ 16918 봄버맨

문제 링크 : 16918번: 봄버맨 (acmicpc.net)

 

16918번: 봄버맨

첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

www.acmicpc.net


2. 풀이 과정

출력 결과에서는 .과 O로만 표시하고 있지만 해당 문제에서는 각 폭탄이 터지는 데까지 걸리는 시간이 있어요. 즉 맵에 O가 여러 개 표시되어 있더라도 각각 터지는 시간은 다를 수 있다는 거예요. 이러한 것을 저는 맵에 0은 빈칸 123은 각 폭탄이 설치되어 있는데 터지기까지 남은 시간을 표시했어요.

 

이문제는 각 폭탄들을 관리하는 것만 생각하면 쉽게 구현할 수 있는 문제였는데 매시간 맵을 검사해서 빈칸이 아닌 곳들은 전부 1씩 감소해주고 

맵을 검사했을 때 1인 부분은 폭탄이 터져야 하므로 벡터에 좌표를 다 넣어놓은 이후에 상하좌우를 0으로 바꿔서 빈칸으로 표시해 줬어요.

 

3. 폭탄 생성 

4. 폭탄 삭제

해당 행위가 반복이기 때문에 현재시간을 2로 나눠서 나머지에 폭탄 생성 함수와 폭발 함수를 번갈아 가면서 실행하게 구현해봤어요.

CreateBomb()을 보시면 폭탄을 새로 생성할 때 3초 후에 폭발하는 거로 표시하는데 처음의 Input()에서는 처음 폭탄을 2초 후에 폭발하는 거로 표시하고 있어요. 이거는

  • 다음 1초 동안 봄버맨은 아무것도 하지 않는다

라는 문항이 있기 때문에 미리 1씩 감소시켜서 맵에 표시해놨어요.


3. 코드

#include <iostream>
#include <vector>

#define Y first
#define X second

using namespace std;

int R, C, N;
int map[201][201];

// 상하좌우
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, -1, 1};

void PrintMap()
{
	for (int y = 0; y < R; y++)
	{
		for (int x = 0; x < C; x++)
		{
			// 0인부분은 빈칸이므로 .으로 바꿔서 출력
			if (map[y][x] == 0)
				cout << ".";
			// 그외에 값은 전부 폭탄이므로 O으로 바꿔서 출력
			else
				cout << "O";
		}
		cout << endl;
	}
}

void Input()
{
	cin >> R >> C >> N;

	for (int y = 0; y < R; y++)
	{
		for (int x = 0; x < C; x++)
		{
			char c;
			cin >> c;
			if (c == '.')
				map[y][x] = 0;
			else
				map[y][x] = 2;
		}
	}
}

void Explosion()
{
	// 폭탄 좌표저장 벡터
	vector<pair<int, int>> v;

	for (int y = 0; y < R; y++)
	{
		for (int x = 0; x < C; x++)
		{
			if (map[y][x] == 1)
			{
				// 터지는 폭탄들 좌표 저장
				v.push_back({ y, x });
			}
		}
	}

	while (!v.empty())
	{
		pair<int, int> cur = v.back();
		v.pop_back();
		map[cur.Y][cur.X] = 0;
		for (int i = 0; i < 4; i++)
		{
			int ny = cur.Y + dy[i];
			int nx = cur.X + dx[i];

			if (ny <0 || nx <0 || ny> R || nx > C)
				continue;
			// 상하좌우 터져서 0(빈칸)으로 만들기
			map[ny][nx] = 0;
		}
	}
}

// 맵 전체를 검사한후 0인부분은 빈칸이므로 폭탄배치
void CreateBomb()
{
	for (int y = 0; y < R; y++)
	{
		for (int x = 0; x < C; x++)
		{
			if (map[y][x] == 0)
				map[y][x] = 3;
		}
	}
}


void Solution()
{
	// 현재시간 
	// 다음 1초 동안 봄버맨은 아무것도 하지 않는다. 그래서 1부터 시작
	int currentTime = 1;

	if (N == 1)
	{
		PrintMap();
		return;
	}
	while (true)
	{		
		// 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다.
		currentTime++;
		// 현재시간이 N초가 지났다면 종료
		if (currentTime > N)
			break;

		for (int y = 0; y < R; y++)
		{
			for (int x = 0; x < C; x++)
			{
				// 2~4은 폭탄을 의미한다.
				// 각 값 -1 은 폭탄이 터지기 까지 남은 시간을 의미
				if (map[y][x] > 1)
				{
					map[y][x] = map[y][x] - 1;
				}
			}
		}

		// 3과 4를 반복한다.
		// 3. 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
		if (currentTime % 2 == 0)
			CreateBomb();
		// 4. 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
		else
			Explosion();
	}
	PrintMap();
}

int main()
{
	Input();
	Solution();
	
	return 0;
}
300x250
300x250

1. 제목

- 백준 3190 뱀

- BOJ 3190 뱀

문제 링크 : 3190번: 뱀 (acmicpc.net)

 

3190번: 뱀

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net


2. 풀이 과정

 

머리와 꼬리라는 문항을 봤을때 저는 앞쪽과 뒤쪽 모두접근이 쉬운 DeQueue를 생각했어요.

먼저 뱀은 몸길이를 늘린다 = DeQueue.front push를 해주고

이동한 칸에 사과가 없다 = Dequeue.back pop을 해주면 쉽게 구현할 수 있어요.

 

매초 시간변수를 증가시키고 이동 위치에 따라 맵에 표시해주면서 시간을 체크해서 현재 시각이 방향을 바꿔야 하는 시간이라면 방향 변환을 해주었어요.

 

 


3. 코드

#include <iostream>
#include <deque>
#include <queue>

#define Y second
#define X first

using namespace std;

int map[102][102];

// N : 맵크기, K : 사과의 개수, L : 뱀의 방향 변환 횟수
int N, K, L;
// 위 오른쪽 아래 왼쪽
int dx[4] = { -1, 0, 1, 0 }; 
int dy[4] = { 0, 1, 0, -1 };
// 방향변수 0 : 위, 1 : 오른쪽, 2 : 아래, 3 : 왼쪽 
int dir;
// 뱀 위치 저장
deque<pair<int, int>> dqSnake;
// 방향 변환 명령어 저장
queue<pair<int, char>> qCommands;
// 시간 변수
int currentTime = 0;

 
// 머리 회전
void Rotate(char command)
{
	if (command == 'D')
		dir = (dir + 1) % 4;
	else
		dir = (dir + 3) % 4;
}

void Solution()
{
	// 뱀 초기값 1행 1열부터 시작
	map[1][1] = 1;
	dqSnake.push_front({1,1});
	// 오른쪽을 보고 시작
	dir = 1;

	while (true)
	{
		currentTime++;
		// 이동방향에 머리 생성
		pair<int, int> head = dqSnake.front();
		// 맨뒤는 꼬리
		pair<int, int> tail = dqSnake.back();
		head.X += dx[dir];
		head.Y += dy[dir];
		dqSnake.push_front(head);

		// 자기 몸통 부딪치거나 맵을 벗어 난다면
		if (map[head.X][head.Y] == 1 ||	head.X < 1 || head.Y < 1 || head.X > N || head.Y > N)
		{
			cout << currentTime << endl;
			return;
		}

		// 이동한 위치에 사과가 없다면
		if (map[head.X][head.Y] != 2)
		{
			// 맵에서 꼬리부분 없애주고 dq에서도 삭제
			map[tail.X][tail.Y] = 0;
			dqSnake.pop_back();
		}
		// 머리부분 1로 표시
		map[head.X][head.Y] = 1;
		// 방향을 바꾸는 명령어가 존재 하면서
		// 현재 시간이 방향을 바꿔야 하는 시간이라면 방향변환
		if (!qCommands.empty() && qCommands.front().first == currentTime)
		{
			Rotate(qCommands.front().second);
			qCommands.pop();
		}
	}
}

void Input()
{
	// 맵크기
	cin >> N;
	cin >> K;
	for (int i = 0; i < K; i++)
	{
		int row, col;
		cin >> row >> col;

		// map
		// 0 = 빈칸, 1 = 뱀, 2 = 아이템
		map[row][col] = 2;
	}
	cin >> L;
	for (int i = 0; i < L; i++)
	{
		int endTime;
		char cDir;
		cin >> endTime >> cDir;

		qCommands.push({endTime, cDir});
	}
}

int main()
{
	Input();
	Solution();

	return 0;
}
300x250
300x250

특정기기에서 보상형 광고를 시청후 게임소리가 안나는 문제가 있어서 이것저것 시도해보고 있어요.

 

    void OnApplicationPause(bool pauseStatus)
    {
        MobileAds.SetApplicationVolume(pauseStatus ? 0f : 0.5f);
    }
MobileAds.SetiOSAppPauseOnBackground(true);

 

Admob을 관리해주는 스크립트에 위 코드들을 추가 해봤어요.

 

플레이어 세팅 값도 확인해 보라고 하는데 전 이미 돼 있더라고요.

Sound was muted forever after minimize app while watching Admob interstitial ad - Unity Forum

 

Sound was muted forever after minimize app while watching Admob interstitial ad

Hello, I have a problem with unity sound on iOS. When my game starting playing an AdMob interstitial ad, I minimize it then re-open again. This will...

forum.unity.com

Sounds are gone just after rewarded ad! · Issue #1516 · googleads/googleads-mobile-unity (github.com)

 

Sounds are gone just after rewarded ad! · Issue #1516 · googleads/googleads-mobile-unity

[REQUIRED] Step 1: Describe your environment Unity version: 2019.4.15f1 Google Mobile Ads Unity plugin version: v5.4.0 Platform: iOS Platform OS version: iOS 14.2 Any specific devices issue occurs ...

github.com

 

[해결]

    void OnApplicationPause(bool pauseStatus)
    {
        AudioSettings.Reset(AudioSettings.GetConfiguration());
    }

앱이 활성화될 때마다 오디오 세팅을 리셋해 주면 사운드가 잘 들립니다.


대부분 기기에서는 위 설정을 안 해줘도 소리 잘 나오던데 특정 기기 때문에 문제 찾느라 힘들었어요.

 

【Unity/iOS】How to solve disappearing audio after AdMob ad played on real device – midolog

 

【Unity/iOS】How to solve disappearing audio after AdMob ad played on real device

This article is a memorandum of how to deal with the mysterious phenomenon of implementing AdMob in Unity. Tab […]

midolog.net

 

300x250
300x250

간단한 게임을 만들어봤어요.

 

Animal Rescue - Google Play 앱

 

Animal Rescue - Google Play 앱

마을주민들을 구해주세요.

play.google.com

 

뱀파이어 서바이벌 같은 게임을 만들어보고 싶어서 만들어 봤는데 다수의 오브젝트를 처리하는 게 쉽지 않네요.
발열 및 렉이 엄청나요...
덕분에 요즘 유니티 DOTS 관련해서 공부 중인데 쉽지 않아요.

300x250
300x250

NullReferenceException: Object reference not set to an instance of an object
  at GPGSManager.<OpenSavedCloud>b__13_0 (GooglePlayGames.BasicApi.SavedGame.SavedGameRequestStatus status, GooglePlayGames.BasicApi.SavedGame.ISavedGameMetadata metaData) [0x00026] in <a9142a370e734de898e2f50617bb764f>:0 
  at GooglePlayGames.Android.AndroidSavedGameClient+<>c__DisplayClass16_1`2[T1,T2].<ToOnGameThread>b__1 () [0x00000] in <ca30eddfbbea4360b18cc3b64e4129d2>:0 
  at GooglePlayGames.OurUtils.PlayGamesHelperObject.Update () [0x0006a] in <ca30eddfbbea4360b18cc3b64e4129d2>:0 

 

구글플레이콘솔 => Play 게임즈 서비스 => 설정 및 관리 => 설정 => 속성수정

저장된 게임 사용 안함을 사용으로 체크해주기.

해결

 

 

300x250
300x250

1. 구글 애드몹 가입하기

 

 

광고를 추가할 어플리케이션을 추가하기위해 앱추가 버튼을 클릭 해주세요.

 

앱이름을 적어주세요.

완료 버튼을 눌러주세요.

 

광고 단위를 눌러주세요.

 

저는 광고보기 버튼을 누르고 봤을때 보상을 주기 위해서 리워드 광고단위를 사용했어요.

 

이름은 마음대로 지으시면 돼요.

 

나중에 여기 있는 아이디를 사용해서 코드에 넣으면돼요.

 

 

 

2. 유니티프로젝트에 패키지 추가하기

 

https://developers.google.com/admob/unity/quick-start?hl=ko

 

시작하기  |  Unity  |  Google Developers

Unity에서 앱을 제작 중인 AdMob 게시자를 위한 모바일 광고 SDK입니다.

developers.google.com

추가가 정상적으로 됐으면 

 

이렇게 나와요.

 

3. 유니티셋팅

 

저기에 앱아이디를 넣어야 하는데 지금은 테스트만 해볼거기 때문에 

 

여기에서 보상형광고 아이디를 테스트용으로 사용 하면됩니다.

 

여기서 주의해야 할게 마지막에 /(슬래시)대신 ~로 바꿔서 넣어줘야 돼요.

 

이곳에 우리에게 필요한 코드가 많이 있어요.

 

UIShop.cs

public class UIShop : MonoBehaviour
{
    private UIHeroShop uiHeroShop;
    public Button btnShowAd;
    public void Init()
    {
        AdMobManager.instance.Init();
        btnShowAd.onClick.AddListener(() =>
        {
            AdMobManager.instance.ShowAds();
        });
    }
}

AdMobManager.cs

using GoogleMobileAds.Api;
using System;
using System.Collections;
using UnityEngine;

public class AdMobManager : MonoBehaviour
{
    private string adUnitId;
    private RewardedAd rewardedAd;

    public static AdMobManager instance;

    public System.Action<Reward> onHandleUserEarnedReward;
    public System.Action<AdFailedToLoadEventArgs> onHandleRewardedAdFailedToLoad;

    public System.Action onHandleRewardedAdFailedToShow;
    public System.Action onHandleRewardedAdClosed;

    private void Awake()
    {
        instance = this;
    }


    public void Init()
    {
        //adUnitId 설정
#if UNITY_EDITOR
        string adUnitId = "unused";
#elif UNITY_ANDROID
        string adUnitId = "ca-app-pub-3940256099942544/5224354917";
#elif UNITY_IPHONE
        string adUnitId = "";
#else
        string adUnitId = "unexpected_platform";
#endif

        // 모바일 광고 SDK를 초기화함.
        MobileAds.Initialize(initStatus => { });

        //광고 로드 : RewardedAd 객체의 loadAd메서드에 AdRequest 인스턴스를 넣음
        AdRequest request = new AdRequest.Builder().Build();
        this.rewardedAd = new RewardedAd(adUnitId);
        this.rewardedAd.LoadAd(request);


        this.rewardedAd.OnAdLoaded += HandleRewardedAdLoaded; // 광고 로드가 완료되면 호출
        this.rewardedAd.OnAdFailedToLoad += HandleRewardedAdFailedToLoad; // 광고 로드가 실패했을 때 호출
        this.rewardedAd.OnAdOpening += HandleRewardedAdOpening; // 광고가 표시될 때 호출(기기 화면을 덮음)
        this.rewardedAd.OnAdFailedToShow += HandleRewardedAdFailedToShow; // 광고 표시가 실패했을 때 호출
        this.rewardedAd.OnUserEarnedReward += HandleUserEarnedReward;// 광고를 시청한 후 보상을 받아야할 때 호출
        this.rewardedAd.OnAdClosed += HandleRewardedAdClosed; // 닫기 버튼을 누르거나 뒤로가기 버튼을 눌러 동영상 광고를 닫을 때 호출
    }
    public void HandleRewardedAdLoaded(object sender, EventArgs args)
    {
        Debug.Log("HandleRewardedAdLoaded");
    }

    public void HandleRewardedAdFailedToLoad(object sender, AdFailedToLoadEventArgs args)
    {
        Debug.Log("HandleRewardedAdFailedToLoad");
        this.onHandleRewardedAdFailedToLoad(args);

    }

    public void HandleRewardedAdOpening(object sender, EventArgs args)
    {
        Debug.Log("HandleRewardedAdOpening");
    }

    public void HandleRewardedAdFailedToShow(object sender, EventArgs args)
    {
        Debug.Log("HandleRewardedAdFailedToShow");
        this.onHandleRewardedAdFailedToShow();
    }

    public void HandleRewardedAdClosed(object sender, EventArgs args)
    {
        Debug.Log("HandleRewardedAdClosed");
        this.onHandleRewardedAdClosed();
    }

    public void HandleUserEarnedReward(object sender, Reward args)
    {
        Debug.Log("HandleUserEarnedReward");
        this.onHandleUserEarnedReward(args);

    }

    public bool IsLoaded()
    {
        return this.rewardedAd.IsLoaded();
    }

    public void ShowAds()
    {
        StartCoroutine(this.ShowAdsRoutine());
    }

    private IEnumerator ShowAdsRoutine()
    {
        while (true)
        {
            bool check = IsLoaded();
            if (check == true)
            {
                this.rewardedAd.Show();
                break;
            }
            else
            {
                Debug.Log("reward ad not loaded.");
            }

            yield return null;
        }
    }
}

 

ID셋팅할때 아까는 /를 ~로 바꿔줬었는데 여기에선 다시 /로 해줘야 돼요.

 

300x250
300x250

1. 제목

- 백준 1931 회의실 배정

- BOJ 1931 회의실 배정

문제 링크 : 1931번: 회의실 배정 (acmicpc.net)

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net


2. 문제 설명

회의실 배정 

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1 복사

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1 복사

4

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

출처

알고리즘 분류


3. 풀이 과정

회의실을 최대한 많이 사용 하려 한다면 회의가 빨리 끝나야 다른 회의도 진행을 할 수가 있어요. 그래서 일단 회의가 일찍 끝나는 팀부터 회의실을 배정해줬습니다. 이렇게 끝나면 간단하겠지만 회의가 동시에 끝나는 경우도 생각을 해줘야 해요.
코드를 보시면 현재 시간을 나타내는 time 변수에 회의실을 배정 할 때마다 (time = 현재회의가 끝나는 시간) 이 들어가고 있는데 이 경우에 
3
1 4
7 7
4 7
이런 예제가 있다면 7 7 팀에 회의실을 배정 해줘 버리면 4 7 팀은 회의실을 배정받을 수 가 없어요. 이러면 때문에 회의 종료 시간이 같다면 시작 시간이 조금이라도 빠른 팀에게 먼저 회의실을 배정해 줘야 최대한 많은 팀이 회의실을 사용할 수가 있어요.


4. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1000 + 1
using namespace std;


struct MeetingTime
{
	int start;
	int end;
};
bool compare(MeetingTime mt1, MeetingTime mt2)
{
	// 종료시간이 같다면
	if (mt1.end == mt2.end)
	{
		// 시작시간이 빠른 순서대로 정렬
		if (mt1.start > mt2.start)
			return false;
		else
			return true;
	}

	// 종료시간이 빠른 순서대로 정렬
	if (mt1.end > mt2.end)
		return false;
	else
		return true;
}

vector<MeetingTime> v;
int N;

int Solution()
{
	int result = 0;

	sort(v.begin(), v.end(), compare);
	// 현재 시간을 나타내는 변수
	int time = 0;
	for (int i = 0; i < v.size(); i++)
	{
		// 현재시간보다 회의실 시작	시간이 늦다면 회의를 시작할 수 있는 상태이다.
		if (v[i].start >= time)
		{
			// 회의를 시작했으므로 현재 시간은 현재 시작한 회의에 종료 시간이 된다.
			time = v[i].end;
			// 회의를 하나 할 때마다 회의실 배정 횟수 1씩 증가시켜주기.
			result++;
		}
	}
	return result;
}

void Input()
{	
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int startTime, endTime;
		cin >> startTime >> endTime;
		v.push_back({ startTime, endTime});
	}
}

int main()
{
	Input();
	cout << Solution() << endl;
	return 0;
}
300x250

'<C++ 백준 BOJ> > 그리디' 카테고리의 다른 글

[백준 BOJ1789] 수들의 합 (C++)  (0) 2023.07.02
[백준 BOJ1026] 보물 (C++)  (0) 2023.07.02
[백준 BOJ2217] 로프 (C++)  (0) 2023.07.02
[백준 BOJ11399] ATM (C++)  (0) 2022.10.10
[백준 BOJ2839] 설탕배달 (C++)  (0) 2022.10.10
300x250

1. 제목

- 백준 11399 ATM

- BOJ 11399 ATM

문제 링크 : 11399번: ATM (acmicpc.net)


2. 문제 설명

ATM 

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

예제 입력 1 복사

5
3 1 4 3 2

예제 출력 1 복사

32

출처

  • 문제를 만든 사람: baekjoon
  • 문제의 오타를 찾은 사람: hakgb11

알고리즘 분류

 


3. 풀이 과정

 

문제 설명에서 친절히 시간이 적은 것부터 처리하면 된다고 알려줘서 입력받은 값들을 오름차순으로 정렬한 후에 누적합을 구해서 더해서 답을 구했어요.


4. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1000 + 1
using namespace std;

int N;
// 데이터 입력을 받을 벡터
vector<int> v;

int Solution()
{
	int result = 0;
	sort(v.begin(), v.end());
	// 누적합을 더하면서 result를 구할 것 이기 때문에 미리 맨 처음 벡터값을 더해 놓는다.
	result += v[0];
	for (int i = 1; i < N; i++)
	{
		// 누적합 구하기
		v[i] += v[i - 1];
		// 누적합들의 합 result에 저장
		result += v[i];
	}
	return result;
}

void Input()
{	
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;
		v.push_back(temp);
	}
}

int main()
{
	Input();
	cout << Solution() << endl;
	return 0;
}
300x250

'<C++ 백준 BOJ> > 그리디' 카테고리의 다른 글

[백준 BOJ1789] 수들의 합 (C++)  (0) 2023.07.02
[백준 BOJ1026] 보물 (C++)  (0) 2023.07.02
[백준 BOJ2217] 로프 (C++)  (0) 2023.07.02
[백준 BOJ1931] 회의실 배정 (C++)  (0) 2022.10.10
[백준 BOJ2839] 설탕배달 (C++)  (0) 2022.10.10
300x250

1. 제목

- 백준 2839 설탕배달

- BOJ 2839 설탕배달

문제 링크 : 2839번: 설탕 배달 (acmicpc.net)

 

2839번: 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그

www.acmicpc.net


2. 문제 설명

설탕 배달 

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

예제 입력 1 복사

18

예제 출력 1 복사

4

예제 입력 2 복사

4

예제 출력 2 복사

-1

예제 입력 3 복사

6

예제 출력 3 복사

2

예제 입력 4 복사

9

예제 출력 4 복사

3

예제 입력 5 복사

11

예제 출력 5 복사

3

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 1번


3. 풀이 과정

 

일단 5개로 나눌 수 있는 최대한의 값을 정해놓고 뺀 후에 나머지가 3으로 나누어떨어질 때까지 1씩 빼보면서 큰 봉지로 나눌 수 있는 최대 갯수를 구했어요.


4. 코드

#include <iostream>
#define MAX 5000 + 1
using namespace std;

int N;

int Solution()
{
	int result = -1;
	int bigBagMaxAmount = N / 5;

	// 일단 큰봉지로 최대한 많이 덜어놓은다음 큰봉지를1개씩 빼보면서 찾는다.
	for (int i = bigBagMaxAmount; i >= 0; i--)
	{
		// n(남은사탕) = (총 사탕의 갯수) - (큰봉지의 갯수 * 5) 
		int n = N - (i * 5);
		// 남은 사탕이 3으로 나누어 떨어지면 답이 구해진다.
		if (n % 3 == 0)
		{
			result = i + (n / 3);
			break;
		}
	}

	return result;
}

void Input()
{
	cin >> N;
}

int main()
{
	Input();
	cout << Solution() << endl;
	return 0;
}
300x250

'<C++ 백준 BOJ> > 그리디' 카테고리의 다른 글

[백준 BOJ1789] 수들의 합 (C++)  (0) 2023.07.02
[백준 BOJ1026] 보물 (C++)  (0) 2023.07.02
[백준 BOJ2217] 로프 (C++)  (0) 2023.07.02
[백준 BOJ1931] 회의실 배정 (C++)  (0) 2022.10.10
[백준 BOJ11399] ATM (C++)  (0) 2022.10.10
300x250

1. 제목

- 백준 5014 스타트링크

- BOJ 5014 스타트링크

문제 링크 : 5014번: 스타트링크 (acmicpc.net)

 

5014번: 스타트링크

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

www.acmicpc.net


2. 문제 설명

스타트링크


시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초  256 MB 35004 11087 8427 33.337%
 
 

문제

강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.

스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.

보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

입력

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

출력

첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.

예제 입력 1 복사

10 1 10 2 1

예제 출력 1 복사

6

예제 입력 2 복사

100 2 1 1 0

예제 출력 2 복사

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2011 D번


3. 풀이 과정

시작 위치에서부터 상하좌우 탐색이 아닌 Up, Down 값만큼 위, 아래 탐색하면서 각각 맵에 걸리는 시간을 1씩 증가시키면서 풀면 되는 문제였어요.

 

초기 셋팅!
발견!


4. 코드

#define MAX 1000000 + 1
#include <iostream>
#include <queue>

using namespace std;

int F, S, G, U, D;
int map[MAX];

void Bfs()
{
	// 큐선언 하고 시작층을 q에 넣어서 시작층부터 탐색하기
	queue<int> q;
	q.push(S);
	map[S] = 1;

	// 시작층이 도착층이라면 바로 끝내버린다.
	if (S == G)
	{
		return;
	}

	// 큐에 더이상 원소가 없을때 까지 탐색하기
	while (!q.empty())
	{
		// cur = 현재층
		// 큐에서 데이터를 하나씩 꺼내서 현재층 위치 바꾸기
		int cur = q.front();
		q.pop();
		// 목표층에 도달을 했다면
		if (cur == G)
			break;

		// 다음 도착층 위로 먼저 올라가보기
		int nextFloor = cur + U;
		// visit배열에 0이 있다면 방문하지 않은 상태입니다.
		// 다음도착층이 꼭대기층 이하여야하고 방문 하지 않았다면 if문 실행

		if (nextFloor <= F && map[nextFloor] == 0)
		{
			// 큐에 다음탐색 출발지점 담아주기
			q.push(nextFloor);
			// 방문체크용 변수에 걸리는 시간도 표현하기 위해 1씩 더해주기
			map[nextFloor] = map[cur] + 1;
		}

		// 다음 도착층은 아래로도 내려가보기
		nextFloor = cur - D;
		// visit배열에 0이 있다면 방문하지 않은 상태입니다.
		// 다음도착층이 0층 이상이여야하고 방문 하지 않았다면 if문 실행
		if (nextFloor >= 1 && map[nextFloor] == 0)
		{
			// 큐에 다음탐색 출발지점 담아주기
			q.push(nextFloor);
			// 방문체크용 변수에 걸리는 시간도 표현하기 위해 1씩 더해주기
			map[nextFloor] = map[cur] + 1;
		}
	}
}

int main()
{
	// F : 꼭대기층, S : 강호위치(시작층), G : 목표층, U : UP버튼을 누를때 마다 올라가는 층수, D : Down버튼을 누를때 마다 내려가는 층수
	cin >> F >> S >> G >> U >> D;

	Bfs();

	// 시작할때 1을 더해주고 시작하니까 1빼고 방문한시간 출력해주기
	if (map[G] != 0)
		cout << map[G]-1 << endl;
	// 모든 탐색을 마쳤는데도 꼭대기층을 방문하지 않았다면 출력해주기
	else
		cout << "use the stairs" << endl;

	return 0;
}
300x250
300x250

1. 제목

- 백준 7562 나이트의 이동

- BOJ 7562 나이트의 이동

문제 링크 :7562번: 나이트의 이동 (acmicpc.net)

 

7562번: 나이트의 이동

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수

www.acmicpc.net


2. 문제 설명

나이트의 이동


시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초  256 MB 41465 20902 15643 49.402%
 

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1 복사

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1 복사

출처

University > Tu-Darmstadt Programming Contest > TUD Contest 2001 3번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: sait2000
  • 문제의 오타를 찾은 사람: sgchoi5
5
28
0

3. 풀이 과정

시작 지점 좌표를 큐에 넣어 놓은 다음 갈 수 있는 모든 지역을 탐색하면서 풀어 봤어요. visit 배열은 따로 사용하지 않았고 대신 각 맵은 시작 지점부터 해당 지점까지 가는 데 걸리는 시간을 저장하는 식으로 -1 라면 도착 지점, 0이라면 아직 방문하지 않은 지역, 1 이상이라면 방문했던 지역이며 이 값은 출발지부터 해당 지점까지 방문하는데 걸리는 시간을 표현 하는 거죠. 그래서 따로 방문처리를 표시할 visit 배열이 필요 없었어요.

 

맵을 처음 구성 할 때 도착지점을 -1 , 시작지점은 1로 표시해두고 

탐색 구역이 -1라면 도착지점을 찾은 것 이므로 처음 시작 지점을 표시하느라 1로 표현 해서 걸리는 시간이 +1 되있으니 지금 지역 도착시간을 바로 넣으면 정답 값이 나오게 돼요


4. 함수 설명

Reset() : 테스트 케이스가 끝날때마다 맵과 큐를 초기상태로 초기화 해주는 작업이 필요해요.

그래서 BFS탐색이 한번 끝날때 마다 맵사이즈만큼 다시 0으로 초기화 해주고 큐에 들은것도 다 제거 해주는 함수에요.

 

 


5. 코드

#define MAX 300 + 1
#define Y first
#define X second
#include <iostream>
#include <queue>

using namespace std;


// 나이트의 탐색 방향 일반적인 상하좌우가 아니에요.
// https://www.acmicpc.net/problem/7562
// 총 8방향이동 하니까 배열도 8개 만들어주기
// 좌상단부터 우상단순으로 넣었어요
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int map[MAX][MAX];
// I : 체스판의 크기는 I*I 이에요
int I;
queue<pair<int, int>> q;

// 테스트 케이스가 끝날때마다 맵과 큐를 초기상태로 초기화 해주는 작업이 필요해요.
void reset()
{
	for (int y = 0; y < I; y++)
	{
		for (int x = 0; x < I; x++)
		{
			map[y][x] = 0;
		}
	}

	while (!q.empty())
		q.pop();
}

void Bfs(int y, int x)
{
	// 시작지점 큐에 넣어놓고
	q.push({y, x});
	// 큐가 빌때까지 BFS 탐색 하기
	while (!q.empty())
	{
		pair<int, int> cur = q.front();
		q.pop();		

		for (int dir = 0; dir < 8; dir++)
		{
			// 8방향 탐색
			int ny = cur.Y + dy[dir];
			int nx = cur.X + dx[dir];

			// 탐색 지점이 맵을 벗어났다면 스킵
			if (ny < 0 || nx < 0 || ny >= I || nx >= I)
				continue;
			// 도착 지점을 찾았다면 현재 맵에 있는 시간을 도착지점에 넣어놓고 탐색을 끝낸다.
			if (map[ny][nx] == -1)
			{
				map[ny][nx] = map[cur.Y][cur.X];
				return;
			}
			// 이미 방문한 지점이라면 스킵한다
			if (map[ny][nx] != 0)
				continue;

			// 맵에는 각지점에 도달하기 까지 걸리는 시간이 들어있는것을 구현하기위해 1씩 더해줌
			map[ny][nx] = map[cur.Y][cur.X] + 1;
			q.push({ny, nx});
				
		}
	}
}

int main()
{
	// t : 테스트케이스 개수
	int t;
	cin >> t;

	// 테스트케이스 개수만큼 실행
	for (int i = 0; i < t; i++)
	{
		// 체스판 크기 설정해주기
		cin >> I;

		// 나이트 시작 지점
		int startY, startX;
		cin >> startY >> startX;
		// 나이트 도착 지점
		int endY, endX;
		cin >> endY >> endX;

		// 시작 지점은 1부터 시작
		map[startY][startX] = 1;
		// 도착 지점은 -1로 표시해두기
		map[endY][endX] = -1;

		// 시작 지점부터 BFS 탐색 시작하기
		Bfs(startY, startX);
		cout << map[endY][endX] << "\n";
		reset();
	}

	return 0;
}
300x250

'<C++ 백준 BOJ> > BFS\DFS' 카테고리의 다른 글

[백준 BOJ5014] 스타트링크 (C++)  (2) 2022.09.18
[백준 BOJ3055] 탈출 (C++)  (0) 2022.09.04
[백준 BOJ5427] 불 (C++)  (0) 2022.09.04
[백준 BOJ6593] 상범 빌딩 (C++)  (0) 2022.09.04
[백준 BOJ2583] 영역 구하기 (C++)  (0) 2022.08.28
300x250

1. 제목

- 백준 3055 탈출

- BOJ 3055 탈출

문제 링크 : 3055번: 탈출 (acmicpc.net)

 

3055번: 탈출

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제

www.acmicpc.net


2. 문제 설명

탈출 


시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 40241 13572 9233 31.863%

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

입력

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

출력

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

예제 입력 1 복사

3 3
D.*
...
.S.

예제 출력 1 복사

3

예제 입력 2 복사

3 3
D.*
...
..S

예제 출력 2 복사

KAKTUS

예제 입력 3 복사

3 6
D...*.
.X.X..
....S.

예제 출력 3 복사

6

예제 입력 4 복사

5 4
.D.*
....
..X.
S.*.
....

예제 출력 4 복사

4

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #1 4번

 

3. 풀이 과정

탐색을 고슴도치가 있는 곳에서도 해야 하고 물이 번져 나가는 곳에서도 해야 해요. 이때 고슴도치는 물이 있는 곳으로 갈 수 없다는 규칙과 물이 찰 예정인 지역으로 이동할 수 없다는 규칙이 있어요. 그러므로 맵에 물이 먼저 번져 나가는 것을 표현시킨 다음 고슴도치를 이동시켜야 해요.
이때 탐색을 할 때 방문할 수 있는 지역을 모두 방문하게 된다면 물을 먼저 탐색시켰을 때 빈공간을 찾아서 전부 물로 바꿔 버리기 때문에 미리 방문 시작할 좌표를 q에 담아놓고 탐색을 시작하기 전 q에 들어간 원소의 개수를 미리 구해놓은 다음 나중에 방문하며 추가로 방문할 수 있는 지역이 있어 원소를 추가하더라도해당 시간에 탐색해야 하는 곳까지만 하게 구현 해야 해요. 고슴도치의 이동도 같은 구조예요.

0초
1초
2초

이렇게 각 한 번씩 탐색을 했을 때마다 시간을 증가시켜서 최종 시간을 구하게 해요. 물이 탐색을 시작할 때 해당 위치에 고슴도치가 있으면 이때 부터는 굳이 물이 번지는 것을 구현할 필요가 없어요. 이미 이 순간부터는 물은 고슴도치를 위협할 수 있는 위치에 없다는 것이니까요.

 


4. 함수 설명

MoveWater() : 물 좌표가 들어있는 q를 상하좌우 탐색하며 물이 번져 나가는 것을 구현하는 함수예요.

MoveS() : 고슴도치의 이동을 구현해주는 함수예요. 고슴도치가 이동을 하기 전 MoveWater()를 호출하여 물이 먼저 움직인 다음 이동하게 했어요.

 


5. 코드

#define MAX 50 + 1
#define X second
#define Y first
#include <iostream>
#include <queue>

using namespace std;

// 상하좌우
int dx[4] = { 0, 0,-1, 1 };
int dy[4] = { 1, -1, 0, 0 };

char map[MAX][MAX];
int R, C;

queue < pair<int, int>> sq;
queue < pair<int, int>> wq;

void MoveWater()
{
	int cnt = wq.size();
	for (int i = 0; i < cnt; i++)
	{
		pair<int, int> cur = wq.front();
		wq.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (ny < 0 || nx < 0 || ny >= R || nx >= C)
				continue;
			if (map[ny][nx] != '.')
				continue;

			map[ny][nx] = '*';
			wq.push({ny, nx});
		}
	}
}

int MoveS()
{
	int time = 0;
	while (!sq.empty())
	{
		time++;
		MoveWater();

		int cnt = sq.size();
		for (int i = 0; i < cnt; i++)
		{
			pair<int, int> cur = sq.front();
			sq.pop();
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];

				if (ny < 0 || nx < 0 || ny >= R || nx >= C)
					continue;
				if (map[ny][nx] == 'D')
					return time;

				if (map[ny][nx] != '.')
					continue;

				map[ny][nx] = 'S';
				sq.push({ny, nx});
			}
		}
	}

	return -1;
}

int main()
{
	cin >> R >> C;

	for (int y = 0; y < R; y++)
	{
		for (int x = 0; x < C; x++)
		{
			cin >> map[y][x];

			if (map[y][x] == 'S')
				sq.push({ y, x });
			else if (map[y][x] == '*')
				wq.push({y, x});
		}
	}	

	int time = MoveS();
	if (time == -1)
		cout << "KAKTUS" << endl;
	else
		cout << time << endl;

	return 0;
}
300x250
300x250

1. 제목


2. 문제 설명

 

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 256 MB 28527 7331 4316 46.933%

문제

 

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

  • '.': 빈 공간
  • '#': 벽
  • '@': 상근이의 시작 위치
  • '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

예제 입력 1 복사

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

예제 출력 1 복사

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2012 F번

 

3. 풀이 과정

BOJ 3055랑 아주 유사한 문제였어요. 풀이 과정이 완전 똑같았어요. 한 턴마다 불과 상근이가 이동해야 하고 불이 먼저 번져 나간 이후에 상근이가 이동해야 문제에서 요구하는 조건인 불이 붙으려는 칸으로 이동할 수 없다를 만족하게 돼요. 그래서 이문제도 q를 2개 구현했고 각각 탐색을 하기 전 미리 q에 들어가 있는 좌표의 개수를 구해놓은 다음 해당 턴에는 탐색을 시작 하기 전 들어 있는 좌표만 탐색하게 진행하게 했어요.

이 문제는 도착 좌표가 따로 정해져 있지 않고 맵을 벗어나게 되면 탈출이라는 규칙을 갖고 있었기에 탐색 범위가 맵을 벗어났을 때 탈출했다는 조건을 줘야 해요.

0초
1초
2초

이제 다음 탐색에 상근이 위치로 불이 번질 텐데 상근이는 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다는 규칙이 있기에 이 순간부터 불은 상근이를 잡을 수가 없어요. 그래서 불은 더 이상 탐색하지 않아요.

 

3초
4초
5초(탈출 성공)

 


4. 함수 설명

MoveFire : 불이 번져 나가는 것을 구현해주는 함수예요.

MoveS : 상근이가 이동하는 함수예요. 탐색 전 MoveFire 를 호출하여 불이 먼저 움직인 다음 상근이가 움직이게 했어요.


5. 코드

#define MAX 1000 + 1
#define X second
#define Y first
#include <iostream>
#include <queue>

using namespace std;

// 상하좌우
int dx[4] = { 0, 0,-1, 1 };
int dy[4] = { 1, -1, 0, 0 };

char map[MAX][MAX];
int w, h;

queue < pair<int, int>> sq;
queue < pair<int, int>> fq;

void MoveFire()
{
	int cnt = fq.size();
	for (int i = 0; i < cnt; i++)
	{
		pair<int, int> cur = fq.front();
		fq.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (ny < 0 || nx < 0 || ny >= h || nx >= w)
				continue;
			if (map[ny][nx] != '.')
				continue;

			map[ny][nx] = '*';
			fq.push({ ny, nx });
		}
	}
}

int MoveS()
{
	int time = 0;
	while (!sq.empty())
	{
		time++;
		MoveFire();

		int cnt = sq.size();
		for (int i = 0; i < cnt; i++)
		{
			pair<int, int> cur = sq.front();
			sq.pop();
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];

				if (ny < 0 || nx < 0 || ny >= h || nx >= w)
					return time;

				if (map[ny][nx] != '.')
					continue;

				map[ny][nx] = '@';
				sq.push({ ny, nx });
			}
		}
	}

	return -1;
}

void Reset(int w, int h)
{
	for (int y = 0; y < h; y++)
	{
		for (int x = 0; x < w; x++)
		{
			map[y][x] = '.';
		}
	}
	while (!sq.empty())
		sq.pop();
	while (!fq.empty())
		fq.pop();
}

int main()
{
	int t;
	cin >> t;	

	for (int i = 0; i < t; i++)
	{
		cin >> w >> h;
		for (int y = 0; y < h; y++)
		{
			for (int x = 0; x < w; x++)
			{
				cin >> map[y][x];

				if (map[y][x] == '@')
					sq.push({ y, x });
				else if (map[y][x] == '*')
					fq.push({ y, x });
			}
		}
		int time = MoveS();
		if (time == -1)
			cout << "IMPOSSIBLE" << endl;
		else
			cout << time << endl;

		Reset(w, h);
	}

	return 0;
}
300x250
300x250

1. 제목


2. 문제 설명

상범 빌딩 

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 13836 5015 3929 36.096%

문제

 

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.

출력

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

예제 입력 1 복사

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

예제 출력 1 복사

Escaped in 11 minute(s).
Trapped!

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 1997 D번


3. 풀이 과정

3차원 문제라 방향 벡터를 기존에 상하좌우에서 위층, 아래층까지 추가 해줘야 하는 문제였어요.
bfs 탐색을 사용하면 시작 지점부터 각 위치까지 도달할 수 있는 시간을 맵에 표현할 수 가 있는데 이 방법을 사용하기 위해서 맵을 문자가 아닌 숫자로 구현했어요.

.(빈공간)        => 0

#(벽)              => 1

E(탈출지점)   => 2

S(시작지점)   => 3

빈공간, 벽, 탈출지점을 표현하느라 시작 지점이 3부터 시작하게 되는데 이러면 맵이 이런 식으로 구현이 돼요.

맵이 구현이 되었다면 0인 지점만 탐색하게 진행하고 2인 지점을 찾게 되면 탈출할 수 있는 것이므로 2인 지점을 찾은 바로 전 지점에서 시간이 1 늘어 날 것이고 처음에 맵을 표현하느라 3부터 시작 했기 때문에 출발지에서 각 지점까지 도착하는데 걸리는 시간은 해당 지점 값 - 3이 되게 될 텐데 제 코드에서는 마지막 도착지는 방문처리를 하지 않고 찾기만 했을 때 바로 시간을 반환시킬 것이기 때문에 -2를 해주면 정답이 돼요.

 


4. 함수 설명

Reset : 테스트 케이스가 여러 개 일 수가 있는데 이때 이전에 있던 데이터들이 남아 있으면 새로운 테스트가 정상적으로 작동하지 않기 때문에 맵과 큐를 비워주는 함수예요.


5. 코드

#define MAX 30 + 1

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct pos
{
	int l, r, c;
};

// 상하좌우 위층, 아래층
int dx[6] = { 0, 0,-1, 1 , 0, 0};
int dy[6] = { 1, -1, 0, 0, 0, 0};
int dl[6] = { 0, 0, 0, 0, 1, -1};

int map[MAX][MAX][MAX];
int L, R, C;

queue <pos> q;

int Bfs()
{
	while (!q.empty())
	{
		pos cur = q.front();
		q.pop();

		// 상하좌우 위층, 아래층
		for (int dir = 0; dir < 6; dir++)
		{
			int nc = cur.c + dx[dir];
			int nr = cur.r + dy[dir];
			int nl = cur.l + dl[dir];

			if (nr < 0 || nc < 0 ||  nl < 0 || nr >= R || nc >= C  || nl >= L)
				continue;
			if (map[nl][nr][nc] == 2)
				return map[cur.l][cur.r][cur.c];
			
			if (map[nl][nr][nc] != 0)
				continue;

			map[nl][nr][nc] = map[cur.l][cur.r][cur.c] + 1;
			q.push({ nl, nr, nc });
		}

	}
	return -1;	
}

void Reset()
{
	for (int l = 0; l < L; l++)
	{
		for (int r = 0; r < R; r++)
		{
			for (int c = 0; c < C; c++)
			{
				map[l][r][c] = '.';
			}
		}
	}
	while (!q.empty())
		q.pop();
}

int main()
{
	// #벽, . 빈칸, S 시작 지점, E 출구
	while(true)
	{
		cin >> L >> R >> C;
		if (L == 0)
			break;

		for (int l = 0; l < L; l++)
		{
			for (int r = 0; r < R; r++)
			{
				for (int c = 0; c < C; c++)
				{
					char ch;
					cin >> ch;

				    if (ch == '.')
					map[l][r][c] = 0;
					else if (ch == '#')
						map[l][r][c] = 1;
					else if (ch == 'E')
						map[l][r][c] = 2;
					else if(ch == 'S')
					{
						map[l][r][c] = 3;
						q.push({ l, r, c });
					}				

				}
			}
		}

		int time = Bfs();
		if (time == -1)
			cout << "Trapped!" << endl;
		else
			cout << "Escaped in " <<  time - 2 << " minute(s)." << endl;

		Reset();		
	}
	return 0;
}
300x250
300x250