[백준] 1743 - 음식물 피하기

1. 문제

1743번: 음식물 피하기

2. 개요

통로 중간중간에 음식물들이 떨어져 있다.

서로 인접한 음식물들은 합쳐져 더 큰 음식물로 변하게 된다.

이 때 통로 내에 있는 가장 큰 음식물의 크기를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

한칸한칸씩 탐색하면서 음식물이 존재하는 구역이라면 visited배열에 넣으면서 DFS를 실행한다.

모든 칸에 대한 탐색이 끝났다면 답을 출력한다.

3-2. Python

import sys
sys.setrecursionlimit(1000000)

N, M, K = map(int, sys.stdin.readline().split())

aisle = [[False for _ in range(M)] for _ in range(N)]
visited = [[False for _ in range(M)] for _ in range(N)]
answer = 0

for i in range(K):
    trash = list(map(int, sys.stdin.readline().split()))
    aisle[trash[0] - 1][trash[1] - 1] = True

def DFS(y, x, cnt):
    dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]

    for i in range(4):
        nextY, nextX = y + dirY[i], x + dirX[i]

        if nextY < 0 or nextY >= N or nextX < 0 or nextX >= M:
            continue

        if aisle[nextY][nextX] == False or visited[nextY][nextX] == True:
            continue
        
        visited[nextY][nextX] = True
        cnt = DFS(nextY, nextX, cnt + 1)

    return cnt

for i in range(N):
    for j in range(M):
        if aisle[i][j] == True:
            visited[i][j] = True
            answer = max(answer, DFS(i, j, 1))

print(answer)

3-3. C#

namespace boj_1743
{
    internal class Program
    {
        static bool[,] aisle;
        static bool[,] visited;
        static int[] dirY = { -1, 0, 1, 0 };
        static int[] dirX = { 0, -1, 0, 1 };
        static int N;
        static int M;

        static void Main(string[] args)
        {
            int answer = 0;

            string[] input = Console.ReadLine().Split();

            N = int.Parse(input[0]);
            M = int.Parse(input[1]);
            int K = int.Parse(input[2]);

            aisle = new bool[N, M];
            visited = new bool[N, M];

            for (int i = 0; i < K; i++)
            {
                int[] trash = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                aisle[trash[0] - 1, trash[1] - 1] = true;
            }

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (aisle[i, j] == true)
                    {
                        visited[i, j] = true;
                        answer = (int)MathF.Max(answer, DFS(i, j, 1));
                    }
                }
            }

            Console.WriteLine(answer);
        }

        static int DFS(int y, int x, int cnt)
        {
            for (int i = 0; i < 4; i++)
            {
                int nextY = y + dirY[i];
                int nextX = x + dirX[i];

                if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
                    continue;

                if (visited[nextY, nextX] == true || aisle[nextY, nextX] == false)
                    continue;

                visited[nextY, nextX] = true;
                cnt = DFS(nextY, nextX, cnt + 1);
            }

            return cnt;
        }
    }
}