[Baekjoon] 15705_단어 찾기

문제(출처: https://www.acmicpc.net/problem/15705)

---

< 단어 찾기 >

 

문제 풀이 

 

연속하는 방향으로 탐색하며 단어 S가 있는지 없는지 확인한다.

 

 my solution (Java)

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

public class _15705_ { // 단어 찾기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		String S = bf.readLine();

		st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		char arr[][] = new char[N][M];
		for (int i = 0; i < N; i++) {
			String str = bf.readLine();
			for (int j = 0; j < M; j++) {
				arr[i][j] = str.charAt(j);
			}
		}

		int dx[] = { -1, 1, 0, 0, -1, -1, 1, 1 };
		int dy[] = { 0, 0, -1, 1, -1, 1, -1, 1 };
		boolean flag = false;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] != S.charAt(0)) {
					continue;
				}
				if (S.length() == 1 || flag) {
					flag = true;
					break;
				}
				for (int k = 0; k < 8; k++) {
					int x = i, y = j, idx = 1;
					while (true) {
						x += dx[k];
						y += dy[k];
						if (x >= 0 && x < N && y >= 0 && y < M && arr[x][y] == S.charAt(idx)) {
							idx++;
						} else {
							break;
						}
						if (idx == S.length()) {
							flag = true;
							break;
						}
					}
					if (flag) {
						break;
					}
				}
			}
			if (flag) {
				break;
			}
		}
		if (flag) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}
}

변수)
S : 단어 S
N, M : 표의 행, 열
arr : 표
dx, dy : 위, 아래, 왼쪽, 오른쪽, 대각선 방향
flag : 단어 존재 여부
x, y, idx : 표 위치, 단어의 찾는 문자 위치

 

단어 S를 입력받는다. 표 크기 N과 M을 입력받은 후 표 정보를 입력받아 저장한다. 표를 탐색하며 단어 S의 첫 번째 문자와 일치하는지 확인한다. 만약 단어가 1글자이거나 단어를 찾았다면 종료한다. 아직 단어를 찾지 못했다면 연속하는 방향으로 이동하며 찾는다. 위, 아래, 왼쪽, 오른쪽, 대각선을 살펴보며 표 범위 안이며 단어 문자와 일치하다면 계속해서 찾는다. 단어를 찾았다면 종료한다.

 

최종 단어를 찾았다면 1을, 못 찾았다면 0을 출력한다.

 

---

---