(백준 - 1245) 농장관리 - 파이썬, 자바

문제(백준 - 1245)

출처 : (https://www.acmicpc.net/problem/1245)

접근

문제를 보면 그래프 탐색임이 한눈에 보입니다.

문제를 이해하고 로직을 정해보았습니다.

1. 산봉우리의 높이가 주변의 봉우리보다 낮다면 False

2. 주변의 산봉우리 중 산봉우리와 동일한 높이가 있다면 탐색한다.

이 로직을 이용하여 코드를 짜보면

코드

자바

import java.io.*;
import java.util.StringTokenizer;


class Main{
	public static int[][] move = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
	public static boolean check;
	// dfs로 높이가 같은 곳으로 이동해서 주변을 살펴본다.
	// 산봉우리를 하나씩 체크한다.
	// 높이가 같다면 이동해서 주변 체크
	public static void dfs(int[][] mountin, boolean[][] visited, int row, int col) {
		int top = mountin[row][col];
		visited[row][col] = true;
		for(int[] m : move) {
			int mrow, mcol;
			mrow = row + m[0];
			mcol = col + m[1];
			if(mrow >= 0 && mcol >= 0 && mrow < mountin.length && mcol < mountin[0].length) {
				if(mountin[mrow][mcol] > top) {
					check = false;
				}
				else if(visited[mrow][mcol] == false && mountin[mrow][mcol] == top)
					dfs(mountin, visited, mrow, mcol);
			}

		}

	}

	// 인접하다 : 상, 하, 좌, 우
	// 산봉우리 : 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합
	// 		   산봉우리 주변의 언덕 높이는 산봉우리보다 작아야 한다.
    public static void main(String[] args) throws IOException{
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	int row, col = 0;
    	StringTokenizer stn = new StringTokenizer(in.readLine());
    	row = Integer.parseInt(stn.nextToken());
    	col = Integer.parseInt(stn.nextToken());
    	int[][] mountin = new int[row][col];
    	boolean[][] visited = new boolean[row][col];
    	
    	// 입력 받아서split하면 string형태의 배열로 반환
    	for(int i = 0; i < row; i++) {
    		StringTokenizer stn1 = new StringTokenizer(in.readLine());
    		for(int k = 0; k < col; k++) {
    			mountin[i][k] = Integer.parseInt(stn1.nextToken());
    			visited[i][k] = false;
    		}
    	}
    	int count = 0;
    	for(int i = 0; i < row; i++) {
    		for(int k = 0; k < col; k++) {
    			if(visited[i][k] == false) {
    				check = true;
    				dfs(mountin, visited, i, k);
    				if(check == true) {
    					count += 1;
    				}
    			}
    		}
    	}
    	System.out.println(count);
    	
    	in.close();
	}
}

파이썬

import sys
input = sys.stdin.readline

# 상, 우, 하, 좌
move = [[-1, 0], [0, 1], [1, 0], [0, -1], [-1, 1], [1, 1], [1, -1], [-1, -1]]

def dfs(row, col):
    # global result
    check = True
    visited[row][col] = True
    top = mountin[row][col]
    for i in move:
        mrow = row + i[0]
        mcol = col + i[1]
        if mrow >= 0 and mcol >= 0 and mrow < len(visited) and mcol < len(visited[0]):
            if mountin[mrow][mcol] > top:
                check = False
            if visited[mrow][mcol] == False and mountin[mrow][mcol] == top:
                dfs(mrow, mcol)
    return check


row, col = map(int, input().strip().split())
mountin = []
for i in range(row):
    mountin.append(list(map(int, input().strip().split())))

visited = [[False] * col for _ in range(row)]
cnt = 0

for i in range(row):
    for k in range(col):
        if mountin[i][k] > 0 and visited[i][k] == False:
            result = dfs(i, k)
            if result == True:
                # print(i, k)
                cnt += 1

print(cnt)

느낀점

코드를 짤 때 코드의 작동 과정을 하나 하나 살펴보면서 짜야 완성도도 높고 정확성이 높다는 것을 느꼈습니다. 재귀를 통하여 dfs 후에 return하여 check를 갱신하려 했으나 쉽지 않았고 탐색을 하는 과정에 있어 걸림돌이 되었습니다. 그렇기 때문에 전역 변수를 놓았고 이 전역변수를 이용하여 결과를 도출하였습니다.