[BOJ1706/Java] 크로스워드

문제 요약과 접근 아이디어

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

1706번: 크로스워드

가로 또는 세로로 여러 개의 단어를 찾아볼 수 있는데 그 중에서 사전식으로 가장 앞에 있는 단어를 찾는 문제이다.

문제를 읽어보면 생각보다 고려할 사항이 많이 없었다.. String 자체에 비교함수가 있으니 그거 쓰면 되고

모든 단어를 찾아 정렬하거나 하는 문제가 아니였어서 가로 세로 탐색하면서 한 단어가 완성되면 현재 최솟값과 비교하면서 min을 갱신하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1706 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        char[][] arr = new char[r][c];
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                arr[i][j] = row.charAt(j);
            }
        }

        String min = String.valueOf((char)('z'+1));
        for (int i = 0; i < r; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j <= c; j++) {
                if (j==c || arr[i][j] == '#') {
                    String tmp = sb.toString();
                    if (tmp.length() >= 2 && min.compareTo(tmp) > 0)
                        min = tmp;
                    sb = new StringBuilder();
                } else {
                    sb.append(arr[i][j]);
                }
            }
        }

        for (int j = 0; j < c; j++) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i <= r; i++) {
                if (i==r || arr[i][j] == '#') {
                    String tmp = sb.toString();
                    if (tmp.length() >= 2 && min.compareTo(tmp) > 0)
                        min = tmp;
                    sb = new StringBuilder();
                } else {
                    sb.append(arr[i][j]);
                }
            }
        }
        System.out.println(min);

	}

}