[코드트리 챌린지] 3주차 - 완전 탐색

지난주 대비 248점 상승!! 800점을 향해 파이팅!!😝

 

 

 

https://www.codetree.ai/cote/14/problems/find-hidden-words-2/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

숨은 단어 찾기 2

 

문제

N과 M이 주어지고 또 N * M의 문자열이 주어지면 가로, 세로, 대각선 뱡향으로 도중에 방향을 틀지 않고 인접하여 나오는 ‘LEE’의 개수를 구하는 프로그램을 작성해 보세요.

 

입력 형식

첫 번째 줄에 정수 N과 M이 공백을 사이에 두고 주어집니다.

• 1 ≤ N, M ≤ 50

출력 형식

첫 번째 줄에 모든 'LEE'의 개수를 출력합니다.

 

입출력 예제

예제 1

입력:

4 6
TAEHGI
EELVWE
LEELSE
HBLUEL

 

출력: 

6

 

예제 설명

아래 그림과 같이 'LEE'의 개수는 총 6개입니다.

 

제한

시간제한: 1000ms
메모리 제한: 80MB

 

---

풀이

arr배열을 순회하며 해당 칸이 "L"이라면 해당 칸 주변의 가로, 세로, 대각선에 대해 탐색을 진행한다.

"E"가 나오는 방향으로 탐색을 계속 진행한다. 주어진 격자 크기를 벗어나거나 "E"가 아닌 다른 칸이 나온다면 탐색을 종료한다.

하나의 칸에 대한 탐색을 멈췄을 때, 해당 칸에서부터 하나의 방향으로 "L", "E", "E"가 존재한다면 result를 증가시킨다.

코드

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (nm[0], nm[1])
let dx = [1, 1, 1, -1, -1, -1, 0, 0]
let dy = [-1, 0, 1, -1, 0, 1, -1, 1]

var arr = [[String]]()
var result = 0

for _ in 0..<n {
    arr.append(readLine()!.map{String($0)})
}

for i in 0..<n {
    for j in 0..<m {
        if arr[i][j] == "L" {
            for idx in 0..<8 {
                var cnt = 1
                var x = i, y = j

                while true {
                    let nx = x+dx[idx]
                    let ny = y+dy[idx]

                    if nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] != "E" {
                        break
                    }
                    cnt += 1
                    x = nx
                    y = ny
                }

                if cnt >= 3 {
                    result += 1
                }
            }
        }
    }
}


print(result)