[Algorithm] 🤞백준 3005 크로스워드 퍼즐 쳐다보기

0. 문제

크로스워드 퍼즐은 R*C크기의 직사각형으로 이루어져 있고, 각 칸은 비어있거나 막혀있다. 퍼즐은 가로(왼쪽->오른쪽) 또는 세로(위->아래)로 연속된 빈 칸에 단어를 채우면서 푼다.

동혁이는 크로스워드 퍼즐을 풀지 않는다. 그는 풀려있는 퍼즐을 쳐다본다. 그런 후에, 그는 그 퍼즐에서 사전순으로 제일 앞서는 단어를 찾는다. (단어는 적어도 2글자이다.)

크로스워드 퍼즐이 주어졌을 때, 사전순으로 제일 앞서는 단어를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 R과 C (2 ≤ R, C ≤ 20)가 주어진다. R는 행의 개수, C는 열의 개수이다. 그 다음 R개의 줄엔 C개의 문자가 포함되어 있다. 각 문자는 영어 알파벳 소문자 또는 '#'이며, '#'인 경우에는 막혀있는 것이다.

출력
첫째 줄에 사전순으로 제일 앞서는 단어를 출력한다. 정답이 항상 존재하는 경우만 입력으로 주어진다.

1. 아이디어

💡 가로(왼쪽→오른쪽)로 2글자 이상인 단어를 찾아 list에 저장
💡 세로(위→아래)로 2글자 이상인 단어를 찾아 list에 저장
💡 단어를 담은 list를 오름차순으로 배열하고 첫번째 단어를 출력

2. 핵심 풀이

1. 가로(왼쪽→오른쪽)로 2글자 이상인 단어를 찾아 list에 저장

for(int i=0; i<r; i++) {
	String tmp = "";
	length = 0;
	for(int j=0; j<c; j++) {
		if(cross[i][j].equals("#")) {
			if(length >= 2) {
				list.add(tmp);
			}
			length = 0;
			tmp = "";
		} else {
			tmp += cross[i][j];
			length++;
		}
	}
	if(tmp.length() >= 2)
		list.add(tmp);
}

2. 세로(위→아래)로 2글자 이상인 단어를 찾아 list에 저장

for(int i=0; i<c; i++) {
	String tmp = "";
	length = 0;
	for(int j=0; j<r; j++) {
		if(cross[j][i].equals("#")) {
			if(length >= 2) {
				list.add(tmp);
			}
			length = 0;
			tmp = "";
		} else {
			tmp += cross[j][i];
			length++;
		}
	}
	if(tmp.length() >= 2)
		list.add(tmp);
}

3. 단어를 담은 list를 오름차순으로 배열하고 첫번째 단어를 출력

Collections.sort(list);

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
public class Imple_12 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		
		int r = Integer.parseInt(s[0]);
		int c = Integer.parseInt(s[1]);
		
		String [][] cross = new String[r][c];
		ArrayList<String> list = new ArrayList<String>();
		
		for(int i=0; i<r; i++) {
			s = br.readLine().split("");
			for(int j=0; j<c; j++) {
				cross[i][j] = s[j];
			}
		}
		
		int length = 0;
		
		for(int i=0; i<r; i++) {
			String tmp = "";
			length = 0;
			for(int j=0; j<c; j++) {
				if(cross[i][j].equals("#")) {
					if(length >= 2) {
						list.add(tmp);
					}
					length = 0;
					tmp = "";
				} else {
					tmp += cross[i][j];
					length++;
				}
			}
			if(tmp.length() >= 2)
				list.add(tmp);
		}
		
		for(int i=0; i<c; i++) {
			String tmp = "";
			length = 0;
			for(int j=0; j<r; j++) {
				if(cross[j][i].equals("#")) {
					if(length >= 2) {
						list.add(tmp);
					}
					length = 0;
					tmp = "";
				} else {
					tmp += cross[j][i];
					length++;
				}
			}
			if(tmp.length() >= 2)
				list.add(tmp);
		}
		
		Collections.sort(list);
		
		System.out.println(list.get(0));
	}

}

4. 결과

성공✨