플러드 필

<canvas id="stage"></canvas><div class="controls"><button id="restart" type="button">처음부터</button><button id="step" type="button">한 단계</button><label>속도 <input id="speed" type="range" min="1" max="5" value="3"></label></div>

body{display:block}#stage{position:absolute;inset:0;width:100%;height:100%}.controls{position:absolute;bottom:9px;left:50%;transform:translateX(-50%);display:flex;align-items:center;gap:7px;white-space:nowrap}.controls button,.controls label{font:12px sans-serif;color:var(--fg);background:var(--surface);border:1px solid var(--line);border-radius:6px;padding:5px 8px}.controls button{cursor:pointer}.controls input{width:75px;vertical-align:middle;accent-color:var(--accent)}@media(max-width:500px){.controls{display:none}}

const frames = [{"kind":"grid","caption":"시작 칸 18을 같은 색으로 채움","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"active":18,"visited":[18]}},{"kind":"grid","caption":"18 방문 · 채운 칸 5개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19],"frontier":[10,26,17,19],"active":18}},{"kind":"grid","caption":"10 방문 · 채운 칸 8개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11],"frontier":[26,17,19,2,9,11],"active":10}},{"kind":"grid","caption":"26 방문 · 채운 칸 11개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27],"frontier":[17,19,2,9,11,34,25,27],"active":26}},{"kind":"grid","caption":"17 방문 · 채운 칸 12개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16],"frontier":[19,2,9,11,34,25,27,16],"active":17}},{"kind":"grid","caption":"19 방문 · 채운 칸 13개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20],"frontier":[2,9,11,34,25,27,16,20],"active":19}},{"kind":"grid","caption":"2 방문 · 채운 칸 15개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3],"frontier":[9,11,34,25,27,16,20,1,3],"active":2}},{"kind":"grid","caption":"9 방문 · 채운 칸 16개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8],"frontier":[11,34,25,27,16,20,1,3,8],"active":9}},{"kind":"grid","caption":"11 방문 · 채운 칸 17개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12],"frontier":[34,25,27,16,20,1,3,8,12],"active":11}},{"kind":"grid","caption":"34 방문 · 채운 칸 18개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35],"frontier":[25,27,16,20,1,3,8,12,35],"active":34}},{"kind":"grid","caption":"25 방문 · 채운 칸 19개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24],"frontier":[27,16,20,1,3,8,12,35,24],"active":25}},{"kind":"grid","caption":"27 방문 · 채운 칸 20개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28],"frontier":[16,20,1,3,8,12,35,24,28],"active":27}},{"kind":"grid","caption":"16 방문 · 채운 칸 20개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28],"frontier":[20,1,3,8,12,35,24,28],"active":16}},{"kind":"grid","caption":"20 방문 · 채운 칸 20개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28],"frontier":[1,3,8,12,35,24,28],"active":20}},{"kind":"grid","caption":"1 방문 · 채운 칸 21개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0],"frontier":[3,8,12,35,24,28,0],"active":1}},{"kind":"grid","caption":"3 방문 · 채운 칸 22개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4],"frontier":[8,12,35,24,28,0,4],"active":3}},{"kind":"grid","caption":"8 방문 · 채운 칸 22개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4],"frontier":[12,35,24,28,0,4],"active":8}},{"kind":"grid","caption":"12 방문 · 채운 칸 22개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4],"frontier":[35,24,28,0,4],"active":12}},{"kind":"grid","caption":"35 방문 · 채운 칸 23개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36],"frontier":[24,28,0,4,36],"active":35}},{"kind":"grid","caption":"24 방문 · 채운 칸 23개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36],"frontier":[28,0,4,36],"active":24}},{"kind":"grid","caption":"28 방문 · 채운 칸 23개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36],"frontier":[0,4,36],"active":28}},{"kind":"grid","caption":"0 방문 · 채운 칸 23개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36],"frontier":[4,36],"active":0}},{"kind":"grid","caption":"4 방문 · 채운 칸 23개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36],"frontier":[36],"active":4}},{"kind":"grid","caption":"36 방문 · 채운 칸 24개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36,37],"frontier":[37],"active":36}},{"kind":"grid","caption":"37 방문 · 채운 칸 25개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36,37,38],"frontier":[38],"active":37}},{"kind":"grid","caption":"38 방문 · 채운 칸 27개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36,37,38,30,39],"frontier":[30,39],"active":38}},{"kind":"grid","caption":"30 방문 · 채운 칸 28개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36,37,38,30,39,22],"frontier":[39,22],"active":30}},{"kind":"grid","caption":"39 방문 · 채운 칸 28개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36,37,38,30,39,22],"frontier":[22],"active":39}},{"kind":"grid","caption":"22 방문 · 채운 칸 30개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36,37,38,30,39,22,14,23],"frontier":[14,23],"active":22}},{"kind":"grid","caption":"14 방문 · 채운 칸 32개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36,37,38,30,39,22,14,23,6,15],"frontier":[23,6,15],"active":14}},{"kind":"grid","caption":"23 방문 · 채운 칸 32개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36,37,38,30,39,22,14,23,6,15],"frontier":[6,15],"active":23}},{"kind":"grid","caption":"6 방문 · 채운 칸 33개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36,37,38,30,39,22,14,23,6,15,7],"frontier":[15,7],"active":6}},{"kind":"grid","caption":"15 방문 · 채운 칸 33개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36,37,38,30,39,22,14,23,6,15,7],"frontier":[7],"active":15}},{"kind":"grid","caption":"7 방문 · 채운 칸 33개","data":{"cols":8,"rows":5,"blocked":[5,13,21,29,31,32,33],"visited":[18,10,26,17,19,2,9,11,34,25,27,16,20,1,3,8,12,35,24,28,0,4,36,37,38,30,39,22,14,23,6,15,7],"frontier":[],"active":7}}];
const title = "플러드 필 · 영역 채우기";
const canvas = document.getElementById('stage');
const ctx = canvas.getContext('2d');
const restart = document.getElementById('restart');
const step = document.getElementById('step');
const speed = document.getElementById('speed');
let index = 0, last = performance.now(), width = 300, height = 200;
function colors(){ const s=getComputedStyle(document.documentElement); const v=(key)=>s.getPropertyValue(key).trim(); return {bg:v('--bg'),fg:v('--fg'),muted:v('--muted'),line:v('--line'),surface:v('--surface'),accent:v('--accent'),accent2:v('--accent-2'),accent3:v('--accent-3')}; }
function resize(){ const dpr=Math.min(devicePixelRatio||1,2); width=innerWidth;height=innerHeight;canvas.width=Math.round(width*dpr);canvas.height=Math.round(height*dpr);ctx.setTransform(dpr,0,0,dpr,0,0);draw(); }
function text(value,x,y,color,size=12,align='left'){ ctx.fillStyle=color;ctx.font='600 '+size+'px sans-serif';ctx.textAlign=align;ctx.textBaseline='middle';ctx.fillText(String(value),x,y); }
function line(x1,y1,x2,y2,color,thick=2){ctx.strokeStyle=color;ctx.lineWidth=thick;ctx.beginPath();ctx.moveTo(x1,y1);ctx.lineTo(x2,y2);ctx.stroke();}
function dot(x,y,r,color){ctx.fillStyle=color;ctx.beginPath();ctx.arc(x,y,r,0,Math.PI*2);ctx.fill();}
function draw(){
  if(!frames.length)return;
  const p=colors(), frame=frames[index], d=frame.data, detail=width>500;
  ctx.fillStyle=p.bg;ctx.fillRect(0,0,width,height);
  text(title,12,18,p.fg,detail?16:13);text(frame.caption,12,detail?43:39,p.muted,detail?13:10);
  text((index+1)+' / '+frames.length,width-12,18,p.muted,10,'right');
  const top=detail?62:53, bottom=detail?height-47:height-9, span=Math.max(10,bottom-top), areaW=Math.min(width-22,detail?710:width-22), left=(width-areaW)/2;
  if(frame.kind==='graph'){
    const nodes=d.nodes, edges=d.edges, positions=Object.fromEntries(nodes.map(n=>[n.id,{x:left+areaW*(.06+.88*n.x),y:top+span*(.11+.78*n.y)}]));
    for(const edge of edges){const a=edge[0],b=edge[1],weight=edge[2],key=[a,b].sort().join('-'),pa=positions[a],pb=positions[b];
      if(d.hideUnvisited&&(!d.visited.includes(a)||!d.visited.includes(b)))continue;
      const chosen=d.selected?.includes(key), active=d.activeEdge===key;ctx.globalAlpha=active||chosen?1:.58;line(pa.x,pa.y,pb.x,pb.y,active?p.accent2:chosen?p.accent:p.muted,active?4:chosen?3:2);ctx.globalAlpha=1;
      if(d.directed){const angle=Math.atan2(pb.y-pa.y,pb.x-pa.x),x=pb.x-Math.cos(angle)*(detail?18:13),y=pb.y-Math.sin(angle)*(detail?18:13);line(x-Math.cos(angle-.55)*7,y-Math.sin(angle-.55)*7,x,y,p.muted,1.5);line(x-Math.cos(angle+.55)*7,y-Math.sin(angle+.55)*7,x,y,p.muted,1.5);}
      if(weight>0&&!d.hideUnvisited)text(weight,(pa.x+pb.x)/2,(pa.y+pb.y)/2-7,p.muted,10,'center');
    }
    for(const node of nodes){if(d.hideUnvisited&&!d.visited.includes(node.id))continue;const pt=positions[node.id],selected=d.visited?.includes(node.id),front=d.frontier?.includes(node.id),active=d.active===node.id;let color=active?p.accent2:front?p.accent3:selected?p.accent:p.surface;
      if(d.groups){const group=d.groups[nodes.findIndex(n=>n.id===node.id)];color=[p.accent,p.accent2,p.accent3][nodes.findIndex(n=>n.id===group)%3];}
      dot(pt.x,pt.y,detail?18:12,color);ctx.strokeStyle=p.line;ctx.lineWidth=1;ctx.stroke();text(node.id,pt.x,pt.y,selected||active||front||d.groups?'#fff':p.fg,detail?13:10,'center');
      if(d.distances)text(Number.isFinite(d.distances[node.id])?d.distances[node.id]:'∞',pt.x,pt.y+(detail?29:22),p.muted,10,'center');
    }
  } else if(frame.kind==='grid'||frame.kind==='table'||frame.kind==='bits'){
    const table=frame.kind==='table',bits=frame.kind==='bits';const rows=bits?1:table?d.values.length:d.rows,cols=bits?d.bits.length:table?d.values[0].length:d.cols;
    const labelX=table?24:0,labelY=table?18:0,cell=Math.min((areaW-labelX)/cols,(span-labelY)/rows,detail?56:32),ox=left+(areaW-(cols*cell+labelX))/2+labelX,oy=top+(span-(rows*cell+labelY))/2+labelY;
    if(table){d.colLabels.forEach((label,c)=>text(label,ox+c*cell+cell/2,oy-10,p.muted,10,'center'));d.rowLabels.forEach((label,r)=>text(label,ox-12,oy+r*cell+cell/2,p.muted,10,'center'));}
    for(let r=0;r<rows;r++)for(let c=0;c<cols;c++){const n=r*cols+c,x=ox+c*cell,y=oy+r*cell,active=bits?d.active?.includes(c):table?d.active?.[0]===r&&d.active?.[1]===c:d.active===n,source=table?d.sources?.some(v=>v[0]===r&&v[1]===c):false,visited=bits?d.bits[c]:table?false:d.visited?.includes(n),front=d.frontier?.includes(n),blocked=d.blocked?.includes(n),path=d.path?.includes(n),queen=d.queens?.[r]===c;
      ctx.fillStyle=blocked?p.line:active?p.accent2:path||queen?p.accent3:front?p.accent2:visited?p.accent:source?p.accent3:bits&&d.bits[c]?p.accent:p.surface;ctx.fillRect(x+2,y+2,cell-4,cell-4);ctx.strokeStyle=p.muted;ctx.globalAlpha=.42;ctx.strokeRect(x+1,y+1,cell-2,cell-2);ctx.globalAlpha=1;
      const value=bits?d.bits[c]:table?d.values[r][c]:queen?'Q':d.start===n?'S':d.goal===n?'G':blocked?'':visited?'·':'';
      if(value!==''&&value!==undefined)text(value,x+cell/2,y+cell/2,(active||path||queen||front||visited||bits&&d.bits[c])?'#fff':p.fg,Math.min(13,cell*.43),'center');
      if(bits)text(c,x+cell/2,y+cell+11,p.muted,9,'center');
    }
  } else if(frame.kind==='intervals'){
    const rowH=Math.min(31,span/d.intervals.length),unit=(areaW-28)/10,ox=left+10,oy=top+(span-rowH*d.intervals.length)/2;
    d.intervals.forEach((it,i)=>{const y=oy+i*rowH;ctx.fillStyle=d.active===i?p.accent2:d.selected.includes(i)?p.accent:p.line;ctx.fillRect(ox+it[0]*unit,y+3,Math.max(5,(it[1]-it[0])*unit-3),rowH-7);text(i+1,ox-5,y+rowH/2,p.muted,10,'right');});
  } else if(frame.kind==='ring'){
    const cx=width/2,cy=top+span/2,r=Math.min(areaW,span)*.35,loc=(v,rr)=>({x:cx+Math.sin(v*2*Math.PI)*rr,y:cy-Math.cos(v*2*Math.PI)*rr});ctx.strokeStyle=p.muted;ctx.globalAlpha=.6;ctx.lineWidth=2;ctx.beginPath();ctx.arc(cx,cy,r,0,Math.PI*2);ctx.stroke();ctx.globalAlpha=1;
    d.keys.forEach((key,i)=>{const point=loc(key,r),server=d.servers.find(s=>s.id===d.owners[i]),dest=loc(server.pos,r);line(point.x,point.y,dest.x,dest.y,d.active===i?p.accent2:p.line,1);dot(point.x,point.y,d.active===i?6:4,d.active===i?p.accent2:p.fg);});
    d.servers.forEach((server,i)=>{const point=loc(server.pos,r);dot(point.x,point.y,detail?15:11,[p.accent,p.accent2,p.accent3,p.fg][i]);text(server.id,point.x,point.y,i===3?p.bg:'#fff',11,'center');});
  } else if(frame.kind==='points'){
    const side=Math.min(areaW,span)-8,ox=(width-side)/2,oy=top+(span-side)/2;ctx.strokeStyle=p.muted;ctx.globalAlpha=.5;ctx.strokeRect(ox,oy,side,side);ctx.globalAlpha=1;ctx.beginPath();ctx.arc(ox,oy+side,side,Math.PI*1.5,0);ctx.strokeStyle=p.muted;ctx.stroke();
    d.points.forEach(([x,y])=>dot(ox+x*side,oy+side-y*side,detail?2.5:1.7,x*x+y*y<=1?p.accent:p.accent2));
  }
}
function advance(){index=(index+1)%frames.length;draw();}
restart.addEventListener('click',()=>{index=0;last=performance.now();draw();});
step.addEventListener('click',()=>{advance();last=performance.now();});
addEventListener('resize',resize);resize();
function loop(now){const delay=900-Number(speed.value)*140;if(now-last>delay){advance();last=now;}requestAnimationFrame(loop);}requestAnimationFrame(loop);