7396. 종구의 딸이름 짓기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWm8hNu6llcDFASj&categoryId=AWm8hNu6llcDFASj&categoryType=CODE

SW Expert Academy

이 문제는 BFS 완전탐색과 함께 다음 검색할 값이 최소값이 되게 하면 되는 문제이다.

<JAVA>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point {
	int x;
	int y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

class Solution {
	static char map[][] = new char[2000][2000];
	static boolean visit[][] = new boolean[2000][2000];
	static int dx[] = { 1, 0 };
	static int dy[] = { 0, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		char name[];
		int n, m;
		for (int t = 1; t <= T; ++t) {
			st = new StringTokenizer(br.readLine(), " ");
			name = new char[4000];
			n = Integer.parseInt(st.nextToken(" "));
			m = Integer.parseInt(st.nextToken());
			for (int i = 0; i < n; ++i) {
				map[i] = br.readLine().toCharArray();
				for (int j = 0; j < m; ++j)
					visit[i][j] = false;
			}
			Queue<Point> q = new LinkedList<>();
			q.add(new Point(0, 0));
			int idx = 1;
			name[0] = map[0][0];
			visit[0][0] = true;
			while (idx < n + m - 1) {
				Queue<Point> nq = new LinkedList<>();
				char _min = 'z' + 1;
				while (!q.isEmpty()) {
					Point cur = q.poll();
					for (int dir = 0; dir < 2; ++dir) {
						int nx = cur.x + dx[dir];
						int ny = cur.y + dy[dir];
						if (nx >= n || ny >= m || visit[nx][ny])
							continue;
						if (map[nx][ny] < _min) {
							nq.clear();
							nq.add(new Point(nx, ny));
							_min = map[nx][ny];
						} else if (map[nx][ny] == _min) {
							nq.add(new Point(nx, ny));
						}
						visit[nx][ny] = true;

					}
				}
				name[idx++] = _min;
				q = nq;
			}
			String s = new String(name);
			System.out.printf("#%d %s\n", t, s);
		}
	}
}

<C++>

#include<iostream>
#include<queue>
using namespace std;
struct Point {
	int x;
	int y;
};
char map[2000][2000];
bool visit[2000][2000];
int dx[] = { 1, 0 };
int dy[] = { 0, 1 };

int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int T;
	cin >> T;
	string name;
	int n, m;
	Point p;
	for (int t = 1; t <= T; ++t) {
		name = "";
		cin >> n >> m;
		for (int i = 0; i < n; ++i) {
			cin >> map[i];
			for (int j = 0; j < m; j++)
				visit[i][j] = false;
		}
		queue<Point> q;
		p.x = 0;
		p.y = 0;
		q.push(p);
		name += map[0][0];
		visit[0][0] = true;
		while (name.length() < n + m - 1) {
			queue<Point> nq;
			char _min = 'z' + 1;
			while (!q.empty()) {
				Point cur = q.front();
				q.pop();
				for (int dir = 0; dir < 2; dir++) {
					int nx = cur.x + dx[dir];
					int ny = cur.y + dy[dir];
					if (nx >= n || ny >= m || visit[nx][ny])
						continue;
					if (map[nx][ny] < _min) {
						while (!nq.empty())
							nq.pop();
						p.x = nx;
						p.y = ny;
						nq.push(p);
						_min = map[nx][ny];
					}
					else if (map[nx][ny] == _min) {
						p.x = nx;
						p.y = ny;
						nq.push(p);
					}
					visit[nx][ny] = true;

				}
			}
			name += _min;
			q = nq;
		}
		cout << "#" << t << " " << name << "\n";
	}
}