코딩생존기

https://www.acmicpc.net/problem/11279

priority_queue를 사용해서 입력받는 수에 따라 push와 pop을 진행해주면 된다. 

정답코드

#include <iostream>
#include <queue>
using namespace std;

int main()
{

	ios::sync_with_stdio(false);  // C와 C++의 I/O 동기화 비활성화
	cin.tie(NULL);  // 입출력 독립 처리

	int n;
	cin >> n;
	priority_queue<int> pq;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		if (x > 0)
		{
			pq.push(x);
		}
		else
		{
			if (!pq.empty())
			{
				cout << pq.top() << "\n";
				pq.pop();
			}
			else
			{
				cout << 0 << "\n";
			}
		}
	}

	return 0;
}

https://www.acmicpc.net/problem/7569

m,n,h값을 통해 3차원 벡터를 초기화 해주고 1인 부분을 queue에 저장하고 이를 BFS방식으로 순회하면서 1인 부분을 추가하고 이 추가한 값을 다시 queue에 넣어서 날마다 반복해주면 된다. 전체 개수와 익은 개수를 비교하기 위해 빈것도 포함해서 개수를 추가해줬다. 

정답코드

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

using namespace std;

// 6방향 이동 (위, 아래, 좌, 우, 앞, 뒤)
int dx[6] = { 0, 0, 0, 0, -1, 1 };
int dy[6] = { 0, 0, -1, 1, 0, 0 };
int dz[6] = { -1, 1, 0, 0, 0, 0 };

int main() {
    int m, n, h;
    cin >> m >> n >> h;

    vector<vector<vector<int>>> tomato(h, vector<vector<int>>(n, vector<int>(m)));
    queue<pair<int, pair<int, int>>> q;  // 큐에 (z, x, y) 좌표 저장

    int empty_count = 0;  // 비어 있는 칸 개수

    // 입력 받기
    for (int z = 0; z < h; z++) {
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                cin >> tomato[z][x][y];
                if (tomato[z][x][y] == 1) {
                    q.push({ z, {x, y} });  // 익은 토마토 위치 큐에 삽입
                }
                else if (tomato[z][x][y] == -1) {
                    empty_count++;  // 비어 있는 칸 카운트
                }
            }
        }
    }

    int total_cells = n * m * h - empty_count;  // 전체 칸에서 비어 있는 칸 제외
    int ripe_count = q.size();  // 초기 익은 토마토 개수
    int days = -1;

    // 이미 모든 토마토가 익어 있는 경우
    if (ripe_count == total_cells) {
        cout << 0 << '\n';
        return 0;
    }

    // BFS 수행
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int z = q.front().first;
            int x = q.front().second.first;
            int y = q.front().second.second;
            q.pop();

            for (int d = 0; d < 6; d++) {
                int nz = z + dz[d];
                int nx = x + dx[d];
                int ny = y + dy[d];

                // 배열 범위 체크 및 익지 않은 토마토 찾아서 익히기
                if (nz >= 0 && nz < h && nx >= 0 && nx < n && ny >= 0 && ny < m && tomato[nz][nx][ny] == 0) {
                    tomato[nz][nx][ny] = 1;  // 익은 토마토로 상태 변경
                    q.push({ nz, {nx, ny} });  // 큐에 추가
                    ripe_count++;  // 익은 토마토 수 증가
                }
            }
        }
        days++;  // 하루가 지나면
    }

    // 모든 칸이 익었는지 확인
    if (ripe_count == total_cells) {
        cout << days << '\n';  // 모든 토마토가 익었으면 소요된 일수 출력
    }
    else {
        cout << -1 << '\n';  // 익지 않은 토마토가 남았으면 -1 출력
    }

    return 0;
}

https://www.acmicpc.net/problem/7576

2차원 벡터를 통해 토마토가 있는 곳을 입력받고 출발점이 되는 1을 모두 큐에 저장하고 이 q를 BFS로 순회하면서 토마토가 있는 곳을 익게하고 이 익은 토마토가 다시 출발점이 되어서 이 큐가 빌때까지 계속하면 된다. 

전체가 다 익었는지 확인하기 위하여 비어있는 토마토의 개수도 같이 세어준다. 

정답코드

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

using namespace std;


int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

int main()
{
	int m, n;
	cin >> m >> n;
	vector<vector<int>> tomato(n, vector<int>(m));
	queue<pair<int, int>> q;		//출발점 큐
	int empty_count = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> tomato[i][j];
			if (tomato[i][j] == 1) {
				q.push({ i, j }); // 익은 토마토의 위치 저장
			}
			else if (tomato[i][j] == -1) {
				empty_count++; // 비어있는 칸 개수 카운트
			}
		}
	}

	int days = -1;
	int total_cells = n * m;
	int ripe_count = q.size() + empty_count; // 초기 익은 토마토와 비어있는 칸
	

	while (!q.empty())
	{
		int size = q.size();
		for (int i = 0; i < size; i++)
		{
			int x = q.front().first;
			int y = q.front().second;
			q.pop();

			for (int d = 0; d < 4; d++)
			{
				int nx = x + dx[d];
				int ny = y + dy[d];

				if (nx >= 0 && nx < n && ny >= 0 && ny < m && tomato[nx][ny] == 0)
				{
					tomato[nx][ny] = 1;
					q.push({ nx,ny });
					ripe_count++;
				}
			}
		}
		days++;
	}

	// 모든 칸이 익었는지 확인
	if (ripe_count == total_cells) {
		cout << days << '\n';
	}
	else {
		cout << -1 << '\n';
	} return 0;

	return 0;
}

이전에 만들었던 대화 출력은 올바르게 되었으니 이제 대화창에서 선택지가 출력되고 이를 선택할 수 있게 만들어주자.

일단 저번에 만들었던 대화를 출력해주는 DialogueManager의 ContinueStory 함수를 수정해주자. 

DialogueManager.cs

public void ContinueStory()
{
    if (currentStory == null) // Null 체크 추가
    {
        Debug.LogError("currentStory가 null입니다!");
        return;
    }

    if (currentStory.canContinue) // 더 보여줄 이야기가 있다면
    {
        popup.displayNameText.text = npcdata.getName();
        popup.portraitImage.sprite = npcdata.getPortrait();
        popup.dialogueText.text = currentStory.Continue(); // 한줄 출력
        DisplayChoices(); // 선택이 있으면 선택 출력
    }
    else
    {
        ExitDialogueMode();
    }
}

오류체크와 선택이 있다면 선택을 출력해주는 함수를 추가해줬다.

이 Display함수는 만약 선택이 있다면 선택의 개수만큼만 버튼을 활성화 시켜주고 나머지는 비활성화시켜준다. 그리고 마지막에 코루틴을 사용하여 첫 항목이 선택되게 한다. 이 코루틴이 있어야 선택이 정상적으로 작동한다.

DialogueManager.cs

 private void DisplayChoices()
 {
     if (popup == null) // Null 체크 추가
     {
         Debug.LogError("팝업 UI가 null입니다!");
         return;
     }

     List<Choice> currentChoices = currentStory.currentChoices;
     if (currentChoices.Count > popup.choices.Length) // 현재 선택지의 개수가 버튼의 개수보다 많으면 오류
     {
         Debug.LogError("More choices than ever");
     }

     int index = 0;
     foreach (Choice choice in currentChoices)
     {
         popup.choices[index].gameObject.SetActive(true);
         popup.choicesText[index].text = choice.text;
         index++;
     }

     for (int i = index; i < popup.choices.Length; i++)
     {
         popup.choices[i].gameObject.SetActive(false);
     }
     popup.choicep.SetActive(true);

     StartCoroutine(SelectFirstChoice());
 }

  private IEnumerator SelectFirstChoice()
  {
      EventSystem.current.SetSelectedGameObject(null);
      yield return new WaitForEndOfFrame();
      EventSystem.current.SetSelectedGameObject(popup.choices[0].gameObject);
  }

그리고 버튼에 OnclickEvent를 추가해주기 위해 MakeChoice함수를 추가하고 이를 Popup을 관리해주는 객체에서 사용하도록 하자.

DialogueManager.cs

public void makeChoice(int choice)
{
    if (currentStory == null) // Null 체크 추가
    {
        Debug.LogError("currentStory가 null입니다!");
        return;
    }

    currentStory.ChooseChoiceIndex(choice);
    ContinueStory();
}

UI_DialioguePopup.cs

private void Start()
{
    for (int i = 0; i < choices.Length; i++)
    {
        int id = i;
        choiceButton[i].onClick.AddListener(() => Managers.Dialogue.makeChoice(id));
    }
}

이렇게 해주면 이제 대화를 진행하면서 선택지가 있으면 선택지를 선택할 수 있게 된다.

이제 다음에는 이 선택지에 따라 퀘스트가 진행되게 만들어볼 것이다.

※매니저에서 코루틴을 사용하는 상황에서 만약 각 매니저가 통합매니저에서 싱글톤으로 관리되고 있다고 하면 사용할 때 New 키워드를 사용하면 nullreferenceexception 에러가 뜬다. 이를 방지하기 위해 GameObject에서 Getcomponent를 통해 해당 매니저를 가져와서 사용해야한다.

https://www.acmicpc.net/problem/1697

최대 범위인 100,000으로 벡터를 초기화해주고 BFS를 통해 탐색을 해주면서 제일 먼저 동생의 위치에 도달하면 그 값을 반환해준다. 이때 현재값에서 -1 +1 *2를  해줘야하기 때문에 이 값을 내부 반복문에 넣고 이를 순회하면서 탐색하도록 해주었다.

정답코드

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

using namespace std;

const int MAX = 100001;

vector<int> v(MAX, 0);

int BFS(int start, int end)
{
	queue<int> q;

	q.push(start);
	v[start] = 1;

	while (!q.empty())
	{
		int curx = q.front();
		q.pop();

		if (curx == end) return v[end] - 1;

		for (int nextx : {curx - 1, curx + 1, 2 * curx})
		{
			//범위검사
			if (nextx >= 0 && nextx < MAX && v[nextx] == 0)
			{
				v[nextx] = v[curx] + 1;
				q.push(nextx);
			}
		}
	}

	return -1;
}


int main()
{
	int n, k;
	cin >> n >> k;


	cout << BFS(n, k) << "\n";

	return 0;
	
}

https://www.acmicpc.net/problem/7562

이 문제는 체스판의 크기를 입력받고 벡터를 초기화 시킨다음 나이트가 갈 수 있는 규칙을 BFS로 탐색하면서 최단거리를 찾을 수 있다면 그 최단거리를 반환해주고 아니라면 0을 반환해준다.

정답코드 

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

using namespace std;

int dx[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

int bfs(int l, int startX, int startY, int endX, int endY)
{
	vector<vector<int>> visited(l, vector<int>(l, 0));
	queue<pair<int, int>> q;
	q.push({ startX, startY });
	visited[startX][startY] = 1;


	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (x == endX && y == endY) return visited[endX][endY] - 1;


		for (int i = 0; i < 8; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx >= 0 && ny >= 0 && nx < l && ny < l && !visited[nx][ny]) {
				visited[nx][ny] = visited[x][y] + 1;
				q.push({ nx, ny });
			}
		}
	}

	return 0;
}


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

	for (int i = 0; i < n; i++)
	{
		int l;
		cin >> l;
		int startX, startY, endX, endY;
		cin >> startX >> startY >> endX >> endY;

		cout << bfs(l, startX, startY, endX, endY) << "\n";
	}
}

https://www.acmicpc.net/problem/1167

우선 트리에 대한 정보를 입력받고 

DFS를 루트노드 1에서 제일 먼 노드를 찾고 그 노드에서 제일 먼 거리를 찾아서 그 거리를 출력해주면 된다.

정답코드

#include <iostream>
#include <vector>
#include <cstring> 

using namespace std;

const int MAX = 100001; // 최대 노드 수
vector<pair<int, int>> tree[MAX]; // 트리를 저장할 인접 리스트 (노드 번호, 거리)
bool visited[MAX]; // 방문 여부를 저장
int maxDistance; // 트리의 지름
int farthestNode; // 가장 먼 노드


void dfs(int node, int distance) {
	visited[node] = true;

	// 최대 거리 갱신
	if (distance > maxDistance) {
		maxDistance = distance;
		farthestNode = node;
	}

	// 연결된 노드 방문
	for (auto next : tree[node]) {
		int nextNode = next.first;
		int nextDistance = next.second;

		if (!visited[nextNode]) {
			dfs(nextNode, distance + nextDistance);
		}
	}
}
int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int node;
		cin >> node;
		while (true)
		{
			int Node, distance;
			cin >> Node;
			if (Node == -1) break;

			cin >> distance;
			tree[node].push_back({ Node,distance });
		}
	}

	memset(visited, false, sizeof(visited));
	maxDistance = 0;
	dfs(1, 0); // 임의의 노드(1번)에서 시작

	// 두 번째 DFS 실행
	memset(visited, false, sizeof(visited));
	maxDistance = 0;
	dfs(farthestNode, 0); // 첫 번째 DFS에서 가장 먼 노드를 시작점으로 설정

	// 트리의 지름 출력
	cout << maxDistance << endl;

	return 0;
}

https://www.acmicpc.net/problem/1991

이진 트리에 대한 정보를 unordered_map을 통해 저장하고 이를 재귀함수를 통해 전위,중위,후위함수를 통해 순회하면서 출력해주면 된다.

정답코드

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<char, pair<char, char>> tree;

//전위 순회
void preorder(char node)
{
	if (node == '.')return;
	cout << node;
	preorder(tree[node].first);
	preorder(tree[node].second);
}
//중위순회
void inorder(char node)
{
	if (node == '.')return;
	inorder(tree[node].first);
	cout << node;
	inorder(tree[node].second);
}
//후위순회
void postorder(char node)
{
	if (node == '.')return;
	postorder(tree[node].first);
	postorder(tree[node].second);
	cout << node;
}

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

	for (int i = 0; i < n; i++)
	{
		char parent, left, right;
		cin >> parent >> left >> right;
		tree[parent] = { left, right }; // 부모와 자식 관계 저장
	}

	preorder('A');
	cout << "\n";
	inorder('A');
	cout << "\n";
	postorder('A');
	cout << "\n";

	return 0;
}

https://www.acmicpc.net/problem/11725

각 노드에 대한 정보를 벡터로 입력받고 이를  BFS로 순회하면서 부모를 지정해주면 된다. 

만약 1에 6과 4가 연결되어 있다면 1은 루트노드이기 때문에 6와 4의 부모는 1이되는것이다.

정답코드

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

using namespace std;

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

	vector<vector<int>> tree(n + 1);
	vector<int>parent(n + 1, 0);

	for (int i = 0; i < n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}


	//BFS
	queue<int> q;
	q.push(1);
	parent[1] = -1;			//루트노드는 부모x

	while (!q.empty())
	{
		int current = q.front();
		q.pop();

		for (int next : tree[current]) {
			if (parent[next] == 0) { // 아직 방문하지 않은 노드
				parent[next] = current; // 부모 기록
				q.push(next);           // 큐에 추가
			}
		}
	}

	// 결과 출력 (2번 노드부터 N번 노드까지의 부모 출력)
	for (int i = 2; i <= n; i++) {
		cout << parent[i] << '\n';
	}

	return 0;
}

https://www.acmicpc.net/problem/11660

2차원 배열에서 구간합을 구해야한다. 이를 위해 누적합을 계산해줘야한다. 이때 문제의 규칙에 맞게

sum[i][j]=arr[i][j]+sum[i−1][j]+sum[i][j−1]−sum[i−1][j−1]

이렇게 더해주면 되는데 이때 

• arr[i][j]
  현재 위치 (i, j)의 값이다. 즉, 현재 칸의 값을 더해야 한다.
• sum[i-1][j]
  (1, 1)부터 (i-1, j)까지의 합이다. 즉, 현재 칸 위쪽에 있는 값들의 합을 포함한다.
• sum[i][j-1]
  (1, 1)부터 (i, j-1)까지의 합이다. 즉, 현재 칸 왼쪽에 있는 값들의 합을 포함한다.
• - sum[i-1][j-1]
  위쪽(sum[i-1][j])과 왼쪽(sum[i][j-1])에서 중복으로 더해진 영역을 빼준다. 중복된 부분은 (1, 1)부터 (i-1, j-1)까지의 합이다.

이렇게 누적합을 계산해주고 쿼리에 맞게 계산된 누적합을 출력해주면 된다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>>v(n + 1, vector<int>(n + 1, 0));
	vector<vector<int>>sum(n + 1, vector<int>(n + 1, 0));

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> v[i][j];
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			sum[i][j] = v[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	}

	for (int i = 0; i < m; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		int result = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
		cout << result << '\n';
	}

	return 0;
}