Baekjoon 1012번 유기농 배추

문제

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

걸린 시간

01 : 57 : 08 실패

문제

Python3

import sys

class Node():
    def __init__(self, v):
        self.vertex = v
        self.link = None

class listGraph():
    def __init__(self):
        self.n = 0 # vertex count
        self.adj_list = []

    # adj_list 의 인덱스를 정점의 번호로 설정
    def insert_vertex(self):
        self.adj_list.append(None)
        self.n += 1

    # v값을 u의 인접 리스트에 삽입
    def insert_edge(self, u, v): 
        new = Node(v)
        if u > self.n-1 or v > self.n-1:
            print("out of area")    
        else:
            new = Node(v)
            new.vertex = v
            new.link = self.adj_list[u]
            self.adj_list[u] = new

def dfs_list(g, v, visited):
    visited[v] = True
    w = g.adj_list[v]
    while w != None:
        if not visited[w.vertex]:
            dfs_list(g, w.vertex, visited)
        w = w.link

def find_connected_component(g, visited):
    count = 0
    for i in range(0, g.n):
        if not visited[i]:
            count += 1
            dfs_list(g, i, visited)
    return count

def adjacency_cabbage(g, u_r, u_c, v_r, v_c, field):
    if v_r < 0 or v_c < 0 or v_r > len(field)-1 or v_c > len(field[0])-1:
        return

    u = field[u_r][u_c] # 현재 배추
    v = field[v_r][v_c] # 인접한 배추

    # 배추가 심어진 위치이면
    if v[0] == 1:
        g.insert_edge(u[1], v[1])

if __name__ == "__main__":
    sys.setrecursionlimit(3000)
    T = int(input())
    result = []            

    for i in range(0, T):
        M, N, K = map(int, input().split())
        g = listGraph()
        cabbage = [list(map(int, input().split())) for _ in range(0, K)]
        field = []

        # 그래프에 정점 추가
        for _ in range(0, K):
            g.insert_vertex()

        visited = [False for _ in range(0, g.n)]

        for i in range(0, N):
            tmp = []
            for j in range(0, M):
                tmp.append([0, None])
            field.append(tmp)

        for i in range(0, K):
            field[cabbage[i][1]][cabbage[i][0]] = [1, i]

        for i in range(0, N):
            for j in range(0, M):
                # 배추가 심어진 위치이면
                if field[i][j][0] == 1:
                    adjacency_cabbage(g, i, j, i, j+1, field) # 상
                    adjacency_cabbage(g, i, j, i, j-1, field) # 하
                    adjacency_cabbage(g, i, j, i-1, j, field) # 좌
                    adjacency_cabbage(g, i, j, i+1, j, field) # 우

        result.append(find_connected_component(g, visited))

    for i in result:
        print(i)

그래프 탐색 방법 dfs, bfs 중 하나를 사용해 연결 성분의 개수를 구하는 문제이다.

입력으로 들어오는 행, 열 값이 가로, 세로의 크기로 주어져 조금 헷갈렸다.

로컬에서는 아무 문제없이 작동했지만 서버에서는 런타임 에러가 발생했다. 원인은 재귀 호출에 있었다. 파이썬에서는 재귀를 무한정 허용할 경우 생길 수 있는 문제들을 고려해 재귀 호출을 1000번으로 제한하고 있다. 노드의 개수가 최대 2500개 까지 있을 수 있는 이번 문제에서는 RecursionError 가 발생할 수 있다.

sys.setrecursionlimit(3000)

위의 문장으로 재귀 호출의 제한을 충분히 늘려주면 런타임 에러가 발생하지 않는다.

TypeScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map((s: string) => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

interface Pair{
  y: number,
  x: number
}

let tc: number = parseInt(input());
const dy: Array<number> = [1, -1, 0, 0];
const dx: Array<number> = [0, 0, -1, 1];

const bfs: Function = (
  sy: number
  , sx: number
  , field: Array<Array<number>>
  , visited: Array<Array<boolean>>
  , n: number
  , m: number
  ) => {
  const queue: Array<Pair> = [{y: sy, x: sx}];
  visited[sy][sx] = true;
  while(queue.length !== 0){
    const size: number = queue.length;
    for(let i = 0; i < size; i++){
      const y: number = queue[0].y;
      const x: number = queue[0].x;
      queue.shift();
      for(let j = 0; j < 4; j++){
        const ny: number = y+dy[j];
        const nx: number = x+dx[j];
        if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
        if(!visited[ny][nx] && field[ny][nx]){
          visited[ny][nx] = true;
          queue.push({y: ny, x: nx});
        }
      }
    }
  }
}

while(tc--){
  const [m, n, k] = input().split(' ').map(Number);
  const field: Array<Array<number>> = Array.from(Array(n), () => Array(m).fill(0));
  const visited: Array<Array<boolean>> = Array.from(Array(n), () => Array(m).fill(false));

  for(let i = 0; i < k; i++){
    const [x, y] = input().split(' ').map(Number);
    field[y][x] = 1;
  }

  let ans = 0;
  for(let r = 0; r < n; r++){
    for(let c = 0; c < m; c++){
      if(field[r][c] && !visited[r][c]){
        bfs(r, c, field, visited, n, m);
        ans++;
      }
    }
  }

  console.log(ans);
}

shift() 만을 이용해 원소를 빼내어 사용하면 TypeScript 에서는 undefined 도 반환되는 값 중의 하나이기 때문에 에러가 발생한다.

맨 앞의 값을 참조한 뒤 shift() 로 값을 제거해주는 방법을 사용해서 해결했다.

참고

• 백준 자유 게시판 - 주로 런타임 에러가 발생하는 이유는 무엇인가요?
• [PYTHON] maximum recursion depth - tmdahr1245