[SWEA] 종구의 딸이름 짓기

Posted on | In |

문제 보러가기

제한사항

이외의 제한사항은 없다.

첫번째 생각

단순한 완전탐색 문제이다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Solution {
	static int N, M;
	static char[][] map;
	static boolean[][] visit;
	static StringBuilder sb;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		int T = Integer.parseInt(br.readLine());
		for(int tc=1;tc<=T;tc++) {
			String[] s = br.readLine().split(" ");
			N = Integer.parseInt(s[0]);
			M = Integer.parseInt(s[1]);
			map = new char[2001][2001];
			visit = new boolean[2001][2001];
			sb = new StringBuilder();
			for (int i = 0; i < N; i++) {
				map[i] = br.readLine().toCharArray(); 
			}
			sb.append(map[0][0]);
			if (M > 1) visit[0][1] = true;
			if (N > 1) visit[1][0] = true;
			char minChar = 'z'; int pivotX = 0; int pivotY = 0;
			for (int i=1; i<M; i++) {
				pivotX = i;
				minChar = 'z';
				for (int j = 0; pivotX >= 0 && j < N; pivotX--, j++) {
					if (!visit[j][pivotX])
						continue;
					if (minChar > map[j][pivotX])
						minChar = map[j][pivotX];
				}
				sb.append(minChar);
				pivotX = i;
				for (int j = 0; pivotX >= 0 && j < N; pivotX--, j++) {
					if (visit[j][pivotX] && minChar == map[j][pivotX]) {
						int tempX = j + 1;
						int tempY = pivotX + 1;
						if (InRange(j, tempY)) 
							visit[j][tempY] = true;
						if (InRange(tempX, pivotX)) 
							visit[tempX][pivotX] = true;
					}
				}
			}
			for (int i = 1; i < N; i++) {
				pivotY = M - 1;
				pivotX = i;
				minChar = 'z';
				while (InRange(pivotX, pivotY)) {
					if (visit[pivotX][pivotY] && (minChar > map[pivotX][pivotY])) {
						minChar = map[pivotX][pivotY];
					}
					pivotY--;
					pivotX++;
				}
				sb.append(minChar);
				pivotY = M - 1;
				pivotX = i;
				while (InRange(pivotX, pivotY)) {
					if (visit[pivotX][pivotY] && map[pivotX][pivotY] == minChar) {
						int tempX = pivotX + 1;
						int tempY = pivotY + 1;
						if (InRange(pivotX, tempY))
							visit[pivotX][tempY] = true;
						if (InRange(tempX, pivotY))
							visit[tempX][pivotY] = true;
					}
					pivotY--;
					pivotX++;
				}
			}

			System.out.println("#"+tc+" "+sb.toString());
		}
	}
	public static boolean InRange(int x, int y) {
		if (x >= 0 && y >= 0 && x < N && y < M) {
			return true;
		}
		return false;

	}
}