[GoLang] 백준 1012번, 유기농 배추 풀어보기

개요

백준의 1012번 문제를 풀어봅시다, 문제는 다 알고 계시겠지만 링크는 아래와 같습니다

https://www.acmicpc.net/problem/1012

요약하자면 

x,y로 된 배추 밭에 값이 1로 묶인 묶음 하나당 배추흰지렁이가 한마리가
필요하다면 전체 밭에서 필요한 배추흰지렁이의 최소 수는?

조건에 묶음이란
상하좌우가 이어진게 한 묶음으로 봅니다 즉 아래 그림은 총 5마리가 필요한 걸 알 수 있습니다.

 

 

다가가기

처음에 문제를 보고 가장 먼저 떠오른 생각은 왼쪽 위 부터 차례대로 오른쪽 아래로 내려오니깐

현재 좌표에서 오른쪽, 아래 값만을 체크하면서 내려오면 되지 않을까라는 생각을 가장 먼저 해봤는데

 

아래와 같은 배추 밭에서는 에서는

 

아래 처럼 왼쪽와 아래에 1이 있을 경우 소거법으로 진행할 경우 성공적으로 소거해나가며

1의 묶음을 셀 수 있지만

아래처럼 뒤집힌 'ㄱ'자에 모양에서는 원래는 1개의 그룹이 되어야하는게 소거법 때문에

2개의 그룹이 되는 예외가 발생하게 됩니다.

그러면 어떻게 해야할까..🤔

 

 

소거법으로 지나간 값을 표현하는 게 아닌 0,1이라는 값과 별개로 지나갔음을 의미하는 값을 추가하기로 했습니다.

 

이번과 같은 경우는 동일한 크기의 bool 배열을 추가해서 체크하면 됩니다.

그리고 하면서 알게 된 점은 아래와 왼쪽 뿐만 아니라 상하좌우를 다 체크해야 아래과 같은 십자가 케이스에서도 정상적으로 실행이 됩니다

 

십자가에서는 [1,0]을 체크하고 [1,1]을 체크하고  [0,1]도 체크를 할 수 있어야 하기 때문

(날먹은 쉽지 않네요)

 

DFS

이 문제는 DSF로 현재 노드 값을 기준으로 연결된 모든 값을 차례대로 접근해가는 알고리즘이 포함되어있습니다.

DFS는 다음 글을 참고하시면 이해하기 편하실 겁니다

https://seung.tistory.com/entry/GoLang-%EB%B0%B1%EC%A4%80-1260%EB%B2%88-DFS%EC%99%80-BFS

[GoLang] 백준 1260번, DFS와 BFS

 

코드

package main

import "fmt"

// 전체 가로 세로 크기, 배추 밭 크기
var maxX, maxY uint8

func main() {
	// 테스트 케이스 수
	var testCase uint8
	// 배추 위치
	var x, y uint8
	// 배추 수
	var count uint16

	fmt.Scanf("%d\n", &testCase)
	for i := uint8(0); i < testCase; i++ {
		fmt.Scanf("%d %d %d\n", &maxX, &maxY, &count)

		// 2차원 배열 값들 초기화
		// 밭
		field := make([][]uint8, maxX)
		// 방문 여부
		visited := make([][]bool, maxX)
		for i := uint8(0); i < maxX; i++ {
			field[i] = make([]uint8, maxY)
			visited[i] = make([]bool, maxY)
		}
		for i := uint16(0); i < count; i++ {
			fmt.Scanf("%d %d\n", &x, &y)
			field[x][y] = 1
		}

		// 배추흰지렁이 수
		var worm = 0
		for i := uint8(0); i < maxX; i++ {
			for j := uint8(0); j < maxY; j++ {
				if field[i][j] == 1 && !visited[i][j] {
					dfs(field, visited, i, j)
					worm++
				}
			}
		}
		fmt.Println(worm)
	}
}

// go에서 이차원 배열의 할당은 슬라이스 내부적을 배열을 참조하기 때문에 이는 간접적으로 이차원 배열의 포인터를 사용하는것과 같음
// => 포인터로 할당 안받아도 됨
func dfs(filed [][]uint8, visited [][]bool, x, y uint8) {
	// 범위를 벗어난 경우 반환
	if x < 0 || x >= maxX || y < 0 || y >= maxY {
		return
	}
	// 배추가 없거나 방문한 경우 반환
	if filed[x][y] == 0 || visited[x][y] {
		return
	}
	visited[x][y] = true
	// dfs 깊이 우선 탐색으로 모든 방향으로 뻗어나가서 체크를 진행한다
	// 이 부분을 반복문으로 바꿀 수 있지만 가독성이 좋지 않아 패스함
	dfs(filed, visited, x+1, y)
	dfs(filed, visited, x-1, y)
	dfs(filed, visited, x, y+1)
	dfs(filed, visited, x, y-1)
}