BOJ 1245 농장 관리

By kuper0201

Published in 알고리즘

2021-03-05

1 min read

문제

입력

풀이

문제

BOJ 1245 농장 관리 바로 가기

농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다.

산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.

문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.

입력

첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다.
둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다.
격자의 높이는 500보다 작거나 같은 음이 아닌 정수이다.

풀이

산봉우리의 개수를 구하는 문제이다.
DFS를 이용해 산봉우리를 찾아내면 된다. 이 때 주의할 점은 문제에서 제시된 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 조건으로 인해 상하좌우 뿐 아니라 대각선의 높이 또한 고려해야 한다는 점이다.

코드 보기(Java)

import java.io.*;

public class Main {
    static int N, M, top = 0;
    static boolean flag = false;
    static int[][] mountain;
    static boolean[][] visit;
    static int[][] dir = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}, {-1, 1}, {-1, -1}, {1, -1}, {1, 1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] info = br.readLine().split(" ");

        N = Integer.parseInt(info[0]);
        M = Integer.parseInt(info[1]);

        mountain = new int[N][M];
        visit = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            info = br.readLine().split(" ");

            for (int j = 0; j < M; j++) {
                mountain[i][j] = Integer.parseInt(info[j]);
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(!visit[i][j]) {
                    flag = false;
                    DFS(i, j);
                    if (!flag) top++;
                }
            }
        }

        System.out.println(top);
    }

    private static void DFS(int x, int y) {
        visit[x][y] = true;

        for (int k = 0; k < 8; k++) {
            int nextX = x + dir[k][0];
            int nextY = y + dir[k][1];

            if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
                if (mountain[nextX][nextY] > mountain[x][y]) flag = true;
                if (!visit[nextX][nextY] && mountain[nextX][nextY] == mountain[x][y]) DFS(nextX, nextY);
            }
        }
    }
}

코드 보기(C++)

#include <iostream>
#define endl '\n'

using namespace std;

int N, M, top = 0;
bool flag = false;
int** mountain;
bool** visit;
int dir[8][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}, {-1, 1}, {-1, -1}, {1, -1}, {1, 1}};

void DFS(int x, int y) {
    visit[x][y] = true;
    
    for (int k = 0; k < 8; k++) {
        int nextX = x + dir[k][0];
        int nextY = y + dir[k][1];

        if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
            if (mountain[nextX][nextY] > mountain[x][y]) flag = true;
            if (!visit[nextX][nextY] && mountain[nextX][nextY] == mountain[x][y]) DFS(nextX, nextY);
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> N >> M;
    
    mountain = new int*[N];
    visit = new bool*[N];
    for(int i = 0; i < N; i++) {
        mountain[i] = new int[M];
        visit[i] = new bool[M];
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> mountain[i][j];
        }
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if(!visit[i][j]) {
                flag = false;
                DFS(i, j);
                if (!flag) top++;
            }
        }
    }

    cout << top << endl;
    return 0;
}

코드 보기(Kotlin)

var top = 0   
var N: Int = 0
var M: Int = 0
var flag = false
var dir = arrayOf(intArrayOf(0, -1), intArrayOf(0, 1), intArrayOf(1, 0), intArrayOf(-1, 0), intArrayOf(-1, 1), intArrayOf(-1, -1), intArrayOf(1, -1), intArrayOf(1, 1))
lateinit var mountain:Array<Array<Int>>
lateinit var visit:Array<Array<Boolean>>

fun DFS(x: Int, y: Int) {
    visit[x][y] = true
    for(k in dir) {
        var nextX: Int = x + k[0]
        var nextY: Int = y + k[1]
        if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
            if(mountain[nextX][nextY] > mountain[x][y]) flag = true
            if(!visit[nextX][nextY] && mountain[nextX][nextY] == mountain[x][y]) DFS(nextX, nextY)
        }
    }
}

fun main() {
    val input = readLine()!!.split(' ')
    N = input[0].toInt()
    M = input[1].toInt()
    
    mountain = Array<Array<Int>>(N){Array<Int>(M){ 0 } }
    visit = Array<Array<Boolean>>(N){Array<Boolean>(M){ false } }

    for(i in 0 until N) {
        val info = readLine()!!.split(' ')
        for(j in 0 until M) mountain[i][j] = info[j].toInt()
    }
    
    for(i in 0 until N) {
        for(j in 0 until M) {
            if(!visit[i][j]) {
                flag = false
                DFS(i, j)
                if(!flag) top += 1
            }
        }
    }
        
    print(top)
}

코드 보기(Python)

top = 0
flag = False
dir = [[0, -1], [0, 1], [1, 0], [-1, 0], [-1, 1], [-1, -1], [1, -1], [1, 1]]

def DFS(x, y):
    global flag
    visit[x][y] = True
    
    for k in dir:
        nextX = x + k[0]
        nextY = y + k[1]
        if nextX >= 0 and nextY >= 0 and nextX < N and nextY < M:
            if mountain[nextX][nextY] > mountain[x][y]:
                flag = True
            if not visit[nextX][nextY] and mountain[nextX][nextY] == mountain[x][y]:
                DFS(nextX, nextY)

def main():
    global N, M, top, flag
    global mountain, visit

    N, M = map(int, input().split())

    mountain = [[0 for col in range(M)] for row in range(N)]
    visit = [[0 for col in range(M)] for row in range(N)]

    for i in range(N):
        info = input().split()

        for j in range(M):
            mountain[i][j] = int(info[j])

    for i in range(N):
        for j in range(M):
            if not visit[i][j]:
                flag = False
                DFS(i, j)
                if not flag:
                    top += 1

    print(top)

if __name__ == "__main__":
    main()

코드 보기(Swift)

import Foundation

var top = 0, M: Int!, N: Int!
var flag = false
let dir = [[0, -1], [0, 1], [1, 0], [-1, 0], [-1, 1], [-1, -1], [1, -1], [1, 1]]
var visit: [[Bool]]!
var mountain: [[Int]]!
  
func DFS(x: Int, y: Int) {
    visit[x][y] = true;
    
    for k in dir {
        let nextX = x + k[0]
        let nextY = y + k[1]
        if nextX >= 0 && nextY >= 0 && nextX < N && nextY < M {
            if mountain[nextX][nextY] > mountain[x][y] {
                flag = true
            }
            
            if !visit[nextX][nextY] && mountain[nextX][nextY] == mountain[x][y] {
                DFS(x: nextX, y: nextY)
            }
        }
    }
}

func main() {
    let inp = readLine()!.components(separatedBy: " ")
    N = Int(inp[0])!
    M = Int(inp[1])!

    mountain = Array(repeating: Array(repeating: 0, count: M), count: N)
    visit = Array(repeating: Array(repeating: false, count: M), count: N)
    
    for i in 0..<N {
        let info = readLine()!.components(separatedBy: " ")

        for j in 0..<M {
            mountain[i][j] = Int(info[j])!
        }
    }
    
    for i in 0..<N {
        for j in 0..<M {
            if !visit[i][j] {
                flag = false
                DFS(x: i, y: j)
                if !flag {
                    top += 1
                }
            }
        }
    }
    print(top)
}

main()