[SWEA 7396] 종구의 딸이름 짓기 (C++, JAVA)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWm8hNu6llcDFASj

SW Expert Academy

1. 주의할 점

- N과 M의 최대 크기가 2000이다 -> DFS 자제

 

2. 구현

- Set을 사용해서 구현해봤다 -> TLE

- DP를 통해서 구현해봤다 -> 메모리초과

- BFS를 이용해서 구현했다 -> 성공 (단, check배열이 없으면 TLE)

 

[JAVA]

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

public class Solution_d5_7396_종구의딸이름짓기 {
	static class Info{
		int x,y;
		public Info(int y, int x) {
			this.x=x;
			this.y=y;
		}
	}
	final static int dx[]= {0,1};
	final static int dy[]= {1,0};
	static int row,col;
	static char arr[][];
	static boolean check[][];
	static String ans;
	static Queue<Info> q;
	static Queue<Info> nq;
	
	static void start() {
		Info ii;
		q=new LinkedList<>();
		nq=new LinkedList<>();
		q.offer(new Info(0,0));
		while (ans.length() < row + col - 1) {
			char c = 'z' + 1;		
			while (!q.isEmpty()) {
				ii = q.poll();
				int cx = ii.x;
				int cy = ii.y;
				for (int i = 0; i < 2; i++) {
					int nx = cx + dx[i];
					int ny = cy + dy[i];
					if (nx < col && ny < row && !check[ny][nx]) {
						check[ny][nx] = true;
						if (arr[ny][nx] < c) {
							c = arr[ny][nx];
							while (!nq.isEmpty()) nq.poll();					
							nq.offer(new Info(ny,nx));
						}
						else if (arr[ny][nx] == c) {
							nq.offer(new Info(ny,nx));
						}
					}
				}
			}
			ans += c;
			q.addAll(nq);
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine().trim());
		for(int t=1;t<=test;t++) {
			String s = br.readLine();
			StringTokenizer st = new StringTokenizer(s," ");
			row = Integer.parseInt(st.nextToken());
			col = Integer.parseInt(st.nextToken());
			//초기화
			arr = new char[row][col];
			check = new boolean[row][col];		
			ans="";
			
			for(int i=0;i<row;i++) 
				arr[i]=br.readLine().toCharArray();
			ans+=arr[0][0];
			check[0][0]=true;
			start();			
			System.out.println("#"+t+" "+ans);
		}
	}
}

 

[C++]

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
char arr[2000][2000];
bool check[2000][2000];
string ans;
int row, col;
int dx[2] = { 0,1 };
int dy[2] = { 1,0 };
struct info {
	int x, y;
};
info tmp;
void start() {
	queue<info> q;
	queue<info> nq;
	tmp.x = 0;
	tmp.y = 0;
	q.push(tmp);
	while (ans.length() < row + col - 1) {
		char c = 'z' + 1;		
		while (!q.empty()) {
			int cx = q.front().x;
			int cy = q.front().y;
			q.pop();
			for (int i = 0; i < 2; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (nx < col && ny < row && !check[ny][nx]) {
					check[ny][nx] = true;
					if (arr[ny][nx] < c) {
						c = arr[ny][nx];
						while (!nq.empty()) nq.pop();
						tmp.x = nx;
						tmp.y = ny;
						nq.push(tmp);
					}
					else if (arr[ny][nx] == c) {
						tmp.x = nx;
						tmp.y = ny;
						nq.push(tmp);
					}
				}
			}
		}
		ans += c;
		q = nq;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test;
	cin >> test;
	for (int t = 1; t <= test; t++) {
		cin >> row >> col;
		for (int i = 0; i < row; i++)
			for (int j = 0; j < col; j++) {
				cin >> arr[i][j];
				check[i][j] = false;
			}
		ans = "";
		ans += arr[0][0];
		check[0][0] = true;
		start();
		cout << "#" << t << " " << ans<<'\n';
	}
	system("pause");
	return 0;
}