[알고리즘] BOJ 21736: 헌내기는 친구가 필요해

태그 BOJGo 분류 알고리즘

BOJ 21736번 문제 "헌내기는 친구가 필요해"를 Go으로 풀이한 글입니다.

chevron_right

목차

문제

링크

solved.ac Silver 2, Class 3

접근

2차원 공간에서 만날 수 있는 사람의 수를 세는 문제로, 전형적인 그래프 탐색 문제이다. 여기서는 구현이 간단한 DFS로 풀어보도록 하자.

풀이

package main

import (
	"bufio"
	"fmt"
	"os"
)

var arr [][]rune
var isVisited [][]bool
var result int = 0
var n int
var m int

func dfs(x, y int) {
	if isVisited[x][y] {
		return
	}

	isVisited[x][y] = true
	if arr[x][y] == 'P' {
		result++
	}

	next := [4][2]int{
		{x + 1, y},
		{x - 1, y},
		{x, y + 1},
		{x, y - 1},
	}

	for _, i := range next {
		if 0 <= i[0] && i[0] < n && 0 <= i[1] && i[1] < m && !isVisited[i[0]][i[1]] && arr[i[0]][i[1]] != 'X' {
			dfs(i[0], i[1])
		}
	}
}

func main() {
	inp := bufio.NewReader(os.Stdin)

	_, _ = fmt.Fscanf(inp, "%d %d\n", &n, &m)

	arr = make([][]rune, n)
	isVisited = make([][]bool, n)
	var startX int
	var startY int

	for i := range n {
		arr[i] = make([]rune, m)
		isVisited[i] = make([]bool, m)
		for j := range m {
			_, _ = fmt.Fscanf(inp, "%c", &arr[i][j])
			if arr[i][j] == 'I' {
				startX = i
				startY = j
			}
			isVisited[i][j] = false
		}
		_, _ = fmt.Fscanf(inp, "\n")
	}

	dfs(startX, startY)

	if result == 0 {
		fmt.Printf("TT\n")
	} else {
		fmt.Printf("%d\n", result)
	}
}

기타

Kotlin으로 풀었을 때, 재귀로 구현하거나 filter를 여러 번 사용했을 경우 시간 초과가 발생했다.

chevron_left
이전 글
[알고리즘] BOJ 1931: 회의실 배정
article
현재 글
[알고리즘] BOJ 21736: 헌내기는 친구가 필요해
인용하기
BibTeX 
@misc{devngho202520251214boj21736,
  author       = {Yu, Dongho},
  title        = {BOJ 21736: 헌내기는 친구가 필요해},
  howpublished = {\url{https://ngho.dev/posts/20251214boj21736}},
  year         = {2025},
  month        = {dec},
  note         = {Accessed: 2025-12-14}
}

APA 유동호. (2025년 12월 14일). BOJ 21736: 헌내기는 친구가 필요해. devngho 블로그. https://ngho.dev/posts/20251214boj21736

Chicago 유동호. “BOJ 21736: 헌내기는 친구가 필요해.” devngho 블로그 (blog). 2025년 12월 14일. https://ngho.dev/posts/20251214boj21736.

MLA 유동호. “BOJ 21736: 헌내기는 친구가 필요해.” devngho 블로그, 2025년 12월 14일, https://ngho.dev/posts/20251214boj21736.