Node.js) 백준 1012번 : 유기농 배추

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

1012번: 유기농 배추

 

단지 번호 붙이기랑 똑같은 문제

 

전체 코드

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n");
const [_,...input2] = input.map(v=>v.split(' ').map(w=>+w));

const answer = [];
const fieldInfo =input2.filter(v=>v.length==3) 
const cabbage = input2.filter(v=>v.length==2)  

fieldInfo.forEach(v=>{
  const column = v[0];
  const row = v[1];
  const cabbageCount = v[2]; 
  let field = Array.from(Array(row+1), () => Array(column+1).fill(0)); 

  
  for(let i = 0; i<cabbageCount; i++){
    let [y,x] = cabbage.shift(); 
    field[x][y] = 1;
  }
  


  const edge = [];
  let marked= []; 
  let adj = []; 

  for(let y = 0; y<row; y++){
    for(let x =0; x<column; x++){
      let now = (column+1)*y+x;
      if(field[y][x]==1){
        if(field[y][x+1]==1){
          edge.push([now,now+1])
        }
        if(field[y+1][x]==1){
          edge.push([now,now+column+1])
        }
        if(field[y][x+1]==0 && field[y+1][x]==0){
          edge.push([now,now])
        }
      }
    }
  }

  for(let i =0; i<(column+1)*(row+1); i++){
    marked[i] = true; 
    adj[i] = [];
  }

  edge.forEach(v=>{
    adj[v[0]].push(v[1])
    adj[v[1]].push(v[0])
    marked[v[0]] = false;
    marked[v[1]] = false;
  })

  function bfs(s){
    let q = [];
    marked[s] = true;
    q.push(s);
    while(q.length>0){
      let v =q.shift();
      adj[v].forEach(w=>{
        if(!marked[w]){
          marked[w]=true;
          q.push(w)
        }
      })
    }

  }

  function check(){
    for(let i = 0; i<marked.length; i++){
      if(marked[i]==false) return i
    }
    return -1;
  }

  let flag = check()
  let bug = 0;
  while(flag>-1){
    bug++;
    bfs(flag);
    flag=check();
  }
  answer.push(bug)
})

console.log(answer.join('\n'))

 

코드 나눠서 해설. 

 

 

1. 배추 밭 정보 알아내기

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n");
const [_,...input2] = input.map(v=>v.split(' ').map(w=>+w));

const answer = [];
const fieldInfo =input2.filter(v=>v.length==3) 
const cabbage = input2.filter(v=>v.length==2)

answer 는 마지막에 출력할 벌레의 개수를 담아 놓기 위한 배열. 

fieldInfo 는 배추 밭의 정보를 모은 배열  ex) [10,8,17]

cabbage는 배추의 위치를 모은 배열 ex) [0,0] [0,1]...

 

 

2. 배추밭 만들고 배추심기. 

fieldInfo.forEach(v=>{
  const column = v[0];
  const row = v[1];
  const cabbageCount = v[2];

fieldInfo 의 정보를 바탕으로 배추밭을 그린다. 

column은 가로 길이 

row는 세로 길이

cabbageCount는 배추 개수 

 

 let field = Array.from(Array(row+1), () => Array(column+1).fill(0));
  for(let i = 0; i<cabbageCount; i++){
    let [y,x] = cabbage.shift();
    field[x][y] = 1;
  }

field 는 배추를 심을 2차원 배열. 

배추	배추
	배추
배추		배추

왼쪽 위부터 한칸씩 옆으로 이동하면서 오른쪽에 배추가 있는지 확인하고 있으면 간선을 연결할꺼임!

마찬가지로 아래쪽에 배추가 있다면 간선 연결! 

=> 오른쪽에 배추있는 지 확인  아래에 배추있는지 확인

그런데 이렇게 하면 제일 오른쪽에 있는 배추들이나 제일 아래 있는 배추들을 검사하기가 복잡해짐.

(핑크색 영역에 있는 배추는 오른쪽이랑 아래에 밭이 있는데 나머지는 밭이 없어서 따로 처리해줘야함) 

그래서 배추밭을 한칸씩 늘려줌.

배추	배추
	배추
배추		배추

 

3.배추끼리 연결하기

 const edge = [];
  for(let y = 0; y<row; y++){
    for(let x =0; x<column; x++){
      let now = (column+1)*y+x;
      if(field[y][x]==1){
        if(field[y][x+1]==1){
          edge.push([now,now+1])
        }
        if(field[y+1][x]==1){
          edge.push([now,now+column+1])
        }
        if(field[y][x+1]==0 && field[y+1][x]==0){
          edge.push([now,now])
        }
      }
    }
  }

칸을 돌면서 배추가 있으면 오른쪽이나 아래를 확인함.

배추 있으면? => 이웃하는 배추라면? 간선을 만들어줌. 

0	1	2	3
4	5	6	7
8	9	10	11
12	13	14	15

각 배추의 좌표를 이런식으로 표현해봤음.  

현재 배추   | 확인할 위치	배추 있는지?	간선 만들기
0 | 1	O	[0,1]
0 | 4	X
1 | 2	X
1 | 5	O	[1,5]
5 | 6	X
5 | 9	X
5| (!6&!9)	X	[5,5]

일단 배추 있는 지 확인하고. 

있으면! 그 오른쪽에 배추가 있는지 확인. 그 아래 배추가 있는 지 확인. 

둘다 없다? 그러면 자기 자신으로 향하는 간선을 하나 만들어 줘야함. 

why? 배추가 외딴 섬처럼 있을 수도 있기 때문. 

 

예를 들어 위의 밭 그림에 10번 배추. 옆에도 배추가 없고. 아래도 배추가 없다? 

그렇다고 아예 간선을 안 넣어주면 간선에서 저 배추를 표시할 방법이 없어짐. 

(( 맨 마지막 조건 없이 배추가 있다면  자기 자신으로 향하는 간선을 만들고 시작해도 될듯?)) 

 

4. 그럼 이제 BFS 하면됨. 

그런데 귀찮다.

 

==========================================================================

 

 

 

내가 작성한 자료구조 알고리즘 글을 봤는데 뭐 설명 하나 없이 문제만 허겁지겁 풀어서 그냥 코드만 딱 붙여놨다.

 

솔직히 아무도 안 볼 것 같다. 

 

그래서 오늘은 문제 풀고 설명  써볼까?? 하고 써봤는데 이거 보통 일이 아니다. 

 

그리고 블로그하려면 그림도 잘 그려야 될 것 같다. 그냥 말로 설명하려니까 엄청 힘들다.

 

블로그 쓰는 사람들 참 대단한 것 같다. 이거 정말 너무 귀찮다. 😉