[C++][JAVA] 백준 - 1012 : 유기농 배추

문제 링크

1012번: 유기농 배추

 

 

풀이 )

  0, 0에서부터 시작해서 배추가 심어진 위치를 찾고 위치를 시작으로 깊이우선탐색을 하고, 끝마치면 방문하지 않은 다음 배추 위치를 찾아 다시 깊이우선탐색을 했다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int field[50][51];
int visited[50][51];
int m, n;

void dfs(int x, int y){
  visited[y][x] = 1;
  for(int dir = 0; dir < 4; ++dir){
    int xx = x+dx[dir];
    int yy = y+dy[dir];
    if(xx < 0 || xx >= m || yy < 0 || yy >= n)
      continue;
    if(field[yy][xx] && !visited[yy][xx])
      dfs(xx, yy);
  }
}

int main(void){
  int t;
  cin >> t;
  while(t--){
    int k;
    cin >> m >> n >> k;
    int ans = 0;
    for(int i = 0; i < n; ++i){
      fill(field[i], field[i]+m, 0);
      fill(visited[i], visited[i]+m, 0);
    }
    for(int i = 0; i < k; ++i){
      int x, y;
      cin >> x >> y;
      field[y][x] = 1;
    }
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < m; ++j){
        if(field[i][j] && !visited[i][j]){
          ans++;
          dfs(j, i);
        }
      }
    }

    cout << ans << endl;
  }
}

 

+ JAVA

BFS와 DFS 2가지 방법으로 풀어봤다.

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    static int n, m, k;
    static boolean[][] board;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String[] in;

        int t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            in = br.readLine().split(" ");
            n = Integer.parseInt(in[1]);
            m = Integer.parseInt(in[0]);
            k = Integer.parseInt(in[2]);
            board = new boolean[n][m];

            while(k-- > 0){
                in = br.readLine().split(" ");
                board[Integer.parseInt(in[1])][Integer.parseInt(in[0])] = true;
            }

            int ans = 0;
            for(int i = 0; i < n; ++i){
                for(int j = 0; j < m; ++j){
                    if(board[i][j]){
                        ans++;
//                        dfs(i, j);
                        bfs(i, j);
                    }
                }
            }

            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }

    static void dfs(int x, int y){
        board[x][y] = false;
        for(int dir = 0; dir < 4; ++dir){
            int nx = x+dx[dir], ny = y+dy[dir];
            if(isIn(nx, ny) && board[nx][ny])
                dfs(nx, ny);
        }
    }

    static void bfs(int x, int y){
        Queue<Point> pointQ = new LinkedList<>();
        pointQ.offer(new Point(x, y));
        board[x][y] = false;
        while(!pointQ.isEmpty()){
            Point cur = pointQ.poll();
            for(int dir = 0; dir < 4; ++dir){
                int nx = cur.x+dx[dir], ny = cur.y+dy[dir];
                if(isIn(nx, ny) && board[nx][ny]){
                    board[nx][ny] = false;
                    pointQ.offer(new Point(nx, ny));
                }
            }
        }
    }

    static boolean isIn(int x, int y){
        return 0 <= x && x < n && 0 <= y && y < m;
    }
}

 

주의 )

  BFS로 풀 때 queue에서 뺄 때 방문 여부를 갱신하는 경우 메모리 초과가 발생하게 된다.

  (같은 좌표에 대해서 queue에 넣을 아직 방문 여부가 갱신되지 않았기 때문에 중복적으로 들어갈 수 있다.)

  따라서 queue에 뺄 때가 아닌 넣을 때 방문 여부를 갱신해야 메모리 초과가 발생하지 않는다.