[Brute Force] 15705번 - 단어찾기

🔗 문제 링크

백준 15705번 - 단어찾기

📝 풀이

처음엔 상하좌우 및 대각선의 모든 방향을 배열로 저장해서
index를 하나하나 증가시켜 문자열을 확인 해야하나 싶었는데
굉장히 비효율적이라는 생각이 들었다.

그렇다면 주어진 단어의 크기에 맞게 문자열을 만들어 StringBuilder에 추가해 문자열을 역순으로 비교하는 것 까지 해결하는 것은 어떨까??

if(sb.toString().equals(word)  ||
				sb.reverse().toString().equals(word)) {
	return true;
}

이 아이디어를 생각해내는데 꽤나 오래 걸렸다.

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

public class 단어찾기_15705 {
	
	public static char[][] map;
	public static int N, M;
	public static String word;
	
	public static boolean findHorizontal() { //가로 탐색
		int size = word.length();
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				int x = i;
				int y = j;
				StringBuilder sb = new StringBuilder();
				
				while(x < M && y < N) {
					if(sb.length() == size) break;
					sb.append(map[x][y]);
					x++;
				}
				
				if(sb.toString().equals(word)||sb.reverse().toString().equals(word)) {
					return true;
				}
			}
			
		}
		
		return false;
		
	}
	
	public static boolean findVertical() { //세로 탐색
		int size = word.length();
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				int x = i;
				int y = j;
				StringBuilder sb = new StringBuilder();
				
				while(x < M && y < N) {
					if(sb.length() == size) break;
					sb.append(map[x][y]);
					y++;
				}
				
				if(sb.toString().equals(word)||sb.reverse().toString().equals(word)) {
					return true;
				}
			}
			
		}
		
		return false;
	}
	
	public static boolean findUpDiagonal() { //상향 대각선
		int size = word.length();
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				int x = i;
				int y = j;
				StringBuilder sb = new StringBuilder();
				
				while(x < M && y > 0) {
					if(sb.length() == size) break;
					sb.append(map[x][y]);
					x++;
					y--;
				}
				
				if(sb.toString().equals(word)||sb.reverse().toString().equals(word)) {
					return true;
				}
			}
			
		}
		
		return false;
	}
	
	public static boolean findDownDiagonal() { //하향 대각선
		int size = word.length();
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				int x = i;
				int y = j;
				StringBuilder sb = new StringBuilder();
				
				while(x < M && y < N) {
					if(sb.length() == size) break;
					sb.append(map[x][y]);
					x++;
					y++;
				}
				
				if(sb.toString().equals(word)||sb.reverse().toString().equals(word)) {
					return true;
				}
			}
			
		}

		return false;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		word = br.readLine();

		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new char[N][M];
		
		for(int i = 0; i < N; i++) {
			String s = br.readLine();
			for(int j = 0; j < M; j++) {
				map[i][j] = s.charAt(j);
			}
		}
		
		if(findHorizontal()) {
			System.out.println("1");
		}
		else if(findVertical()) {
			System.out.println("1");
		}
		else if(findDownDiagonal()) {
			System.out.println("1");
		}
		else if(findUpDiagonal()) {
			System.out.println("1");
		}
		else System.out.println("0");
			
	}
}