백준 6118. 크로스워드 퍼즐 쳐다보기(java) / 시뮬레이션

@시뮬레이션

간단한 시뮬레이션 문제

어려워 보이는데 별로 어렵지는 않다. 단지 풀면서 이게 맞나...? 싶었을 뿐.

+그리고 처음에 문제 이해할 때 약간 알쏭달쏭했다.

 

#

구현 방법

1. findStart()

- 이중 for문을 돌면서 첫 행 또는 첫 열에서 시작하거나, 이전 문자가 #인 출발점을 찾는다. 이렇게 하면 시작점을 찾을 수 있다.

 

2. horizenWord(), vertiWord()

- 찾은 시작점에서 수직(위->아래), 수평(왼쪽->오른쪽) 방향으로 단어를 찾고, 단어의 길이가 2 이상인 경우에만 리스트에 추가한다.

 

3. findFirst()

- 리스트에 있는 단어들 중에서 사전순으로 가장 앞에있는 단어를 찾는다. 일단 첫 글자부터 비교하고,. 첫 글자가 같은 경우 가장 긴 단어의 길이(20)만큼 for문을 돌면서 각 자리의 글자를 비교한다.

- a와 aa 둘 중에서 사전순으로 a가 먼저 와야 하는데, index가 1일 때 char배열의 초기값인 '\0'와 'a'를 비교하면 0 < 97이므로 a가 선택된다.

 

 

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

public class Main {
	
	private static int r, c, ans;
	private static char[][] map;
	private static ArrayList<char[]> list;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		map = new char[r][c];
		list = new ArrayList<>();
		
		for (int i = 0; i < r; i++)
			map[i] = br.readLine().toCharArray();
		
		findStart();
		findFirst();
		
		String rslt = "";
		for (char c : list.get(ans)) {
			if (c == '\0') break;
			rslt += c;
		}
		System.out.println(rslt);
	}

	private static void findFirst() {
		for (int i = 1; i < list.size(); i++) {
			if (list.get(i)[0] < list.get(ans)[0])
				ans = i;
			else if (list.get(i)[0] == list.get(ans)[0]) {
				for (int j = 1; j < 20; j++) {
					if (list.get(i)[j] < list.get(ans)[j]) {
						ans = i;
						break;
					} else if (list.get(i)[j] == list.get(ans)[j]) {
						continue;
					} else {
						break;
					}
				}
			}
		}
	}

	private static void findStart() {
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (map[i][j] == '#') continue;
				
				if (i == 0)
					vertiWord(i, j);
				else if (map[i - 1][j] == '#')
					vertiWord(i, j);
				
				if (j == 0)
					horizonWord(i, j);
				else if (map[i][j - 1] == '#')
					horizonWord(i, j);
			}
		}
	}

	private static void horizonWord(int x, int y) {
		char[] arr = new char[20];
		int idx = 0;
		
		for (int j = y; j < c; j++) {
			if (map[x][j] == '#') break;
			arr[idx++] = map[x][j];
		}
		if (idx >= 2) list.add(arr);
	}
	
	private static void vertiWord(int x, int y) {
		char[] arr = new char[20];
		int idx = 0;
		
		for (int i = x; i < r; i++) {
			if (map[i][y] == '#') break;
			arr[idx++] = map[i][y];
		}
		if (idx >= 2) list.add(arr);
	}
}

#

삽질 포인트

별로 어려운 문제는 아니었는데, 사전순으로 앞에 오는 단어를 찾는 과정에서 어처구니 없는 실수를 해서 찾느라 조금 고생했다.

인덱스를 전혀 뜬금없는 값으로 넣고 해서.. (근데 테케는 맞게 나와서 찾느라 조금 고생함)

 

난이도는 중하 정도인 문제였다.

끝!