IBM Korea Skip to main content
       IBM Ȩ    |  Á¦Ç° & ¼­ºñ½º  |  °í°´Áö¿ø & ´Ù¿î·Îµå  |  È¸¿ø°¡ÀÔ  

ÀÚ¹Ù ÃÖÀûÈ­ ±â¼ú
¸ñ Â÷:
½ÇÇà ¼Ö·ç¼Ç
¾Ë°í¸®Áò °³¼±
Áß°£ °á°ú ij½ÌÇϱâ
ÇÁ·Î±×·¡¹Ö ÃÖÀûÈ­
°á·Ð
Âü°íÀÚ·á
ÇÊÀÚ¼Ò°³
±â»ç¿¡ ´ëÇÑ Æò°¡
°ü·Ã dW ¸µÅ©:
Merlin brings nonblocking I/O to the Java platform
Improve the performance of your Java code
Subscribe to the developerWorks newsletter
US ¿ø¹® Àбâ
Also in the Java zone:
Tutorials
Tools and products
Code and components
Articles
ÀÚ¹Ù ¾ÖÇø®ÄÉÀ̼ÇÀÇ ÆÛÆ÷¸Õ½º Çâ»óÀ» À§ÇÑ ½ÇÁú °¡À̵å

Erwin Vervaet, ¼ÒÇÁÆ®¿þ¾î ¿£Áö´Ï¾î, Ervacon
Maarten De Cock, ¾ÖÇø®ÄÉÀÌ¼Ç ¿£Áö´Ï¾î, ASQdotCOM

2002³â 6¿ù

ÀÚ¹Ù ÇÁ·Î±×·¥À» ÃÖÀûÈ­ ÇÒ ¼ö ÀÖ´Â À¯¿ëÇÑ ±â¼úµéÀÌ ¸¹ÀÌ ÀÖ´Ù. ÀÌ ±Û¿¡¼­´Â ƯÁ¤ ±â¼ú Çϳª¿¡ Æ÷Ä¿½º¸¦ ¸ÂÃß´Â °Í ´ë½Å ÃÖÀûÈ­ ÇÁ·Î¼¼½º¸¦ ÀüüÀûÀ¸·Î ´Ù·é´Ù. °£´ÜÇÑ ±â¼ú ÆÁ¿¡¼­ºÎÅÍ °í±Þ ¾Ë°í¸®Áò ÃÖÀûÈ­±îÁö ´Ù¾çÇÑ ±â¼úµéÀ» ¼¼ºÐÈ­ÇÏ¿© ¹®Á¦ ÇØ°á ÇÁ·Î±×·¥ÀÇ ÆÛÆ÷¸Õ½º Æ©´×À» ÇÑ´Ù.

´ëºÎºÐÀÇ ÀÚ¹Ù ÆÛÆ÷¸Õ½º °ü·Ã ±ÛµéÀº ÇÁ·Î±×·¡¸ÓµéÀÌ ÇÁ·Î±×·¥ ¼Óµµ¸¦ Çâ»ó½ÃÅ°´Âµ¥ Àû¿ëÇÒ ¼ö ÀÖ´Â ±â¼ú¿¡ ÃÊÁ¡À» ¸ÂÃß°í ÀÖ´Ù. ÀÌ ±Û¿¡¼­´Â StringBuffer Ŭ·¡½º °°Àº °£´ÜÇÑ ÇÁ·Î±×·¡¹Ö À̵ð¾öÀ» ºñ·ÔÇÏ¿©, °´Ã¼ ij½Ã(object caches)ÀÇ »ç¿ë °°Àº °í±Þ ±â¼úÀ» ¼³¸íÇÏ°Ú´Ù.

¿ì¸®°¡ °³¹ßÇÏ°í ÃÖÀûÈ­ ÇÒ ÇÁ·Î±×·¥Àº Meteor ÆÛÁñ¿¡ ´ëÇÑ ¸ðµç °¡´ÉÇÑ ¼Ö·ç¼ÇÀ» °è»êÇÒ °ÍÀÌ´Ù. Meteor ÆÛÁñÀº 10°³ÀÇ ÆÛÁñ Á¶°¢°ú 5°³ÀÇ À°°¢ÇüÀ¸·Î ±¸¼ºµÈ ´Ù¸¥ »ö»óµé·Î ÀÌ·ç¾îÁ® ÀÖ´Ù (°¢ º¯ÀÇ ±æÀÌ°¡ °°Àº À°¸éÀÇ ´Ù°¢ÇüÀÌ´Ù). ÆÛÁñ º¸µå ÀÚü´Â °¡·Î 5 x ¼¼·Î 10 ÆÐÅÏÀ¸·Î ·¹À̾ƿôÀº 50°³ÀÇ À°°¢ÇüÀ» ¸ð¾Æ Á÷»ç°¢Çü ÇüÅ°¡ µÈ´Ù. 10°³ÀÇ Á¶°¢À» »ç¿ëÇÏ¿© Àüü º¸µå¸¦ ä¿ö¼­ ÆÛÁñÀ» Ç® ¼ö ÀÖ´Ù. ÀÌ ÆÛÁñ¿¡ ´ëÇÑ ¼Ö·ç¼ÇÀº ±×¸² 1ÀÌ µÈ´Ù.

Eternity ÆÛÁñ
ÀÌ ±Û¿¡ ¼Ò°³µÈ ÀÚ¹Ù ÇÁ·Î±×·¥ÀÌ 10 Á¶°¢ÀÇ Meteor ÆÛÁñÀ» Ǫ´Â °ÍÀ̶ó¸é ÁøÂ¥ ¸ñÇ¥´Â ÈξÀ Å« 209 Á¶°¢ÀÇ ÆÛÁñÀ» Ǫ´Â °ÍÀÌ¿´´Ù. ÀÌ°ÍÀº Christopher MoncktonÀÌ °í¾ÈÇÑ °ÍÀ¸·Î 1999³â 6¿ù¿¡ ¿µ±¹¿¡¼­ ¼Ò°³µÇ¾ú´Ù. ÆÛÁñ À̸§Àº Eternity ÆÛÁñÀÌ´Ù. Eternity ÆÛÁñÀÌ ¹ßÇ¥µÊ°ú µ¿½Ã¿¡ MoncktonÀº ´Ù¾çÇÑ ÀÛÀº ÆÛÁñµéÀ» ¹ßÇ¥Çϱ⠽ÃÀÛÇß´Ù. Meteor, Delta, Heart µîÀÌ ±×°ÍÀÌ´Ù. 1¹é¿À½Ê¸¸ ´Þ·¯ »ó´çÀÇ »ó±ÝÀÌ ÀÌ ÆÛÁñÀ» Ǫ´Â »ç¶÷¿¡°Ô Á¦°øµÇ¾ú´Ù. 2000³â 5¿ù 15ÀÏ¿¡ Alex Selby¿Í Oliver Riordan¿¡°Ô µ¹¾Æ°¬´Ù. µÎ ¹ø° ¼Ö·ç¼ÇÀº ³ªÁß¿¡ Guenter Stertenbrink°¡ ¹ß°ßÇß´Ù. Àç¹Õ°Ôµµ ÀÌ ¼Ö·ç¼Ç Áß ¾î¶²°Íµµ Christopher°¡ ¹Ì¸® ¸¸µé¾îµÐ 6°³ÀÇ ´Ü¼­¿Í ¸ÂÁö ¾Ê¾Ò´Ù. ÀÌ´Â ¾ÆÁ÷µµ ¾Ë·ÁÁöÁö ¾Ê°í ÀÖ´Ù.

±×¸² 1. Meteor ÆÛÁñ Ç®ÀÌ


Ç®ÀÌ°¡ ¾ÆÁÖ °£´ÜÇغ¸ÀÌ´Â ¸¸Å­ ÄÄÇ»ÅÍ ÇÁ·Î±×·¥ÀÇ ±¸Çö¿¡ ÀÖ¾î Áß¿äÇÑ ¹®Á¦ÀÌ´Ù. ÀÌ ÇÁ·Î±×·¥À» ÀÛ¼ºÇÏ´Â °ÍÀº ¸¹Àº ´Ù¸¥ ÀÚ¹Ù ÆÛÆ÷¸Õ½º °ü·Ã ¾ÆƼŬ¿¡¼­ ãÀ» ¼ö ÀÖ´Â ¿¹Á¦¿Í´Â ´Ù¸¥ °ÍÀ» Á¦°øÇÑ´Ù. ÀÌ°ÍÀº ¸¹Àº ÃÖÀûÈ­ ±â¼úÀ» ³ªÅ¸³¾ ¼ö ÀÖ°í ±×µéÀ» Á¶ÇÕÇÏ´Â ¹æ¹ýÀ» ³ªÅ¸³¾ ¼ö ÀÖ´Ù. ÃÖÀûÈ­ ÀÛ¾÷À» ½ÃÀÛÇϱâ Àü¿¡ ½ÇÇà ¼Ö·ç¼ÇÀ» °³¹ßÇØ¾ß ÇÑ´Ù.

½ÇÇà ¼Ö·ç¼Ç
ÀÌ ¼½¼Ç¿¡¼­´Â ÆÛÁñ Ç®ÀÌ ÇÁ·Î±×·¥ÀÇ Ãʱ⠱¸Çö¿¡ ´ëÇØ À̾߱âÇÒ °ÍÀÌ´Ù. ¿©±â¿¡´Â »ó´çÈ÷ ¸¹Àº ÄÚµå Á¶°¢µéÀÌ Æ÷ÇԵǾî ÀÖ´Ù. µû¶ó¼­ Àγ»½ÉÀ» °¡Á®¾ßÇÑ´Ù. ÀÏ´Ü ±âº» ¾Ë°í¸®ÁòÀ» ¼³¸íÇÏ°í ³ª¼­ ÃÖÀûÈ­¸¦ ½ÃÀÛÇÑ´Ù. ÀÌ Ãʱ⠱¸Çö¿¡ ¾²ÀÎ ¼Ò½ºÄÚµå »Ó¸¸¾Æ´Ï¶ó ÃÖÀûÈ­ ¼Ò½ºÄÚµå´Â Âü°íÀÚ·á¿¡¼­ ÀÌ¿ëÇÒ ¼ö ÀÖ´Ù.

ÆÛÁñ Ç®ÀÌ ¾Ë°í¸®Áò
ÀÌ ÆÛÁñ Ç®ÀÌ ÇÁ·Î±×·¥Àº Meteor ÆÛÁñ¿¡ ´ëÇØ ¸ðµç °¡´ÉÇÑ ¼Ö·ç¼ÇÀ» °è»êÇÑ´Ù. ÀÌ´Â Á¶°¢µéÀ» »ç¿ëÇÏ¿© º¸µå¸¦ ä¿ï ¼ö ÀÖ´Â ¸ðµç °¡´ÉÇÑ ¹æ¹ýÀ» »ô»ôÀÌ Ã£¾Æ¾ß ÇÔÀ» ÀǹÌÇÑ´Ù. ÀÌ·¯ÇÑ ÀÛ¾÷ÀÇ Ã¹ ¹ø° ´Ü°è´Â Á¶°¢¿¡ ´ëÇØ ¸ðµç ¼ø¿­À» °áÁ¤ÇÏ´Â °ÍÀÌ´Ù. ¼ø¿­Àº º¸µå¿¡ Á¶°¢µéÀ» À§Ä¡½ÃÅ°´Â ¹æ¹ýÀÌ´Ù. ¸ðµç Á¶°¢ÀÌ ¾ÕµÚ·Î µÚÁý¾îÁú ¼ö ÀÖ°í ¿©¼¸ °³ÀÇ º¯ Áß Çϳª°¡ ´Ù¸¥ ¿©¼¸°³ÀÇ º¯ ÁÖÀ§·Î ȸÀüµÉ ¼ö ÀÖ´Ù´Â °ÍÀ» ¾È´Ù¸é º¸µåÀÇ ÇÑ À§Ä¡¿¡ Á¶°¢À» ³ÖÀ» ¼ö ÀÖ´Â ÃÑ 12°¡ÁöÀÇ °¡´ÉÇÑ ¹æ¹ýÀÌ ÀÖ´Ù´Â °Í¿¡ µµ´ÞÇÑ´Ù. º¸µåÀÇ 50°³ÀÇ À§Ä¡°¡ ÀÖÀ¸¹Ç·Î ÇϳªÀÇ Á¶°¢À» º¸µå¿¡ ³ÖÀ» ¸ðµç °¡´ÉÇÑ ¹æ¹ýÀº 600 (2 x 6 x 50)°¡Áö ÀÌ´Ù.

¹°·Ð ÀÌ ¸ðµç °¡´É¼ºµéÀÌ ½ÇÁ¦·Î ÀÛµ¿ÇÏ´Â °ÍÀº ¾Æ´Ï´Ù. ¸ðµç Á¶°¢µé¿¡ ´ëÇØ ÀÌ·¯ÇÑ ÇÁ·Î¼¼½º¸¦ ¹Ýº¹Çϸé Á¶°¢À» »ç¿ëÇÏ¿© °¡´ÉÇÑ ¸ðµç ä¿ì±â¸¦ ½ÃµµÇÔÀ¸·Î¼­ ¸ðµç °¡´ÉÇÑ ¼Ö·ç¼ÇÀ» ãÀ» ù ¹ø° ¾Ë°í¸®Áò¿¡ À̸¥´Ù. Listing 1Àº ÀÌ ¾Ë°í¸®Áò ÄÚµåÀÌ´Ù. pieceList¶ó°í ºÒ¸®´Â °£´ÜÇÑ ArrayList¸¦ »ç¿ëÇÏ¿© ¸ðµç Á¶°¢µéÀ» º¸À¯ÇÒ ¼ö ÀÖ´Ù. board °´Ã¼´Â ÆÛÁñ º¸µå¸¦ ³ªÅ¸³½´Ù.

Listing 1. ÃʱâÀÇ ÆÛÁñ Ç®ÀÌ ¾Ë°í¸®Áò

public void solve() {
  if (!pieceList.isEmpty()) {
    // Take the first available piece
    Piece currentPiece = (Piece)pieceList.remove(0);

    for (int i = 0; i < Piece.NUMBEROFPERMUTATIONS; i++) {
      Piece permutation = currentPiece.nextPermutation();

      for (int j = 0; j < Board.NUMBEROFCELLS; j++) {
        if (board.placePiece(permutation, j)) {
          
          /* We have now put a piece on the board, so we have to
             continue this process with the next piece by 
             recursively calling the solve() method */
          
          solve();
          
          /* We're back from the recursion and we have to continue
             searching at this level, so we remove the piece we
             just added from the board */
          
          board.removePiece(permutation);
        }
        // Else the permutation doesn't fit on the board
      }
    }

    // We're done with this piece
    pieceList.add(0, currentPiece);
  }
  else {
    
    /* All pieces have been placed on the board so we
       have found a solution! */
    
    puzzleSolved();
  }
}

±âº» ¾Ë°í¸®ÁòÀ» ¼³Á¤ÇßÀ¸´Ï µÎ °¡Áö ´Ù¸¥ Áß¿äÇÑ ¹®Á¦µéÀ» ¿¬±¸ÇØ¾ß ÇÑ´Ù:

  • ÇÑ Á¶°¢ÀÇ ÆÛÁñÀ» ¾î¶»°Ô ³ªÅ¸³¾ °ÍÀΰ¡?
  • ÆÛÁñ º¸µå¸¦ ¾î¶»°Ô ±¸ÇöÇÒ °ÍÀΰ¡?

Listing 1¿¡ ³ª¿ÍÀÖ´Â ¾Ë°í¸®Áò¿¡¼­ Piece Ŭ·¡½º¿Í Board Ŭ·¡½º¸¦ »ç¿ëÇß´Ù. µÎ °¡Áö Ŭ·¡½ºÀÇ ±¸Çö¿¡ ´ëÇØ ¾Ë¾Æº¸ÀÚ.

Piece Ŭ·¡½º
Piece Ŭ·¡½º¸¦ ¼³°èÇϱâ Àü¿¡, ÀÌ Å¬·¡½º°¡ ¹«¾ùÀ» ³ªÅ³¾°ÍÀÎÁö¸¦ »ý°¢ÇØ¾ß ÇÑ´Ù. ±×¸² 2¸¦ º¸¸é, Meteor ÆÛÁñ Á¶°¢ÀÌ ´Ù¼¸°³ÀÇ ¼¿·Î ¿¬°áµÇ¾î ÀÖ´Ù´Â °ÍÀ» ¾Ë ¼ö ÀÖ´Ù. °¢ ¼¿Àº 6 º¯(side)À» °¡Áø Á¤À°°¢ÇüÀÌ´Ù: EAST, SOUTHEAST, SOUTHWEST, WEST, NORTHWEST, NORTHEAST. ÇÑ Á¶ °¢ÀÇ µÎ ¼¿ÀÌ Æ¯Á¤ÇÑ º¯¿¡¼­ ¸¸³¯ ¶§ ¿ì¸®´Â ÀÌ·¯ÇÑ ¼¿µéÀ» ÀÌ¿ô(neighbour)À̶ó°í ºÎ¸¥´Ù. °á±¹, Piece °´Ã¼´Â ´ÜÁö ´Ù¼¸ °³ÀÇ ¿¬°áµÈ Cell °´Ã¼¿¡ Áö³ªÁö ¾Ê´Â´Ù. °¢ Cell °´Ã¼´Â ¿©¼¸ °³ÀÇ º¯°ú ¿©¼¸ °³ÀÇ °¡´ÉÇÑ ÀÌ¿ô ¼¿µéÀ» °¡Áö°í ÀÖ´Ù. Cell Ŭ·¡½º ±¸ÇöÀº ´Ü¼øÇÏ´Ù (Listing 2). Cell °´Ã¼¿¡¼­ processed Ç÷¡±×¸¦ °ü¸®ÇÑ´Ù´Â °ÍÀ» ÁÖ¸ñÇ϶ó. ³ªÁß¿¡ ¹«ÇÑ ·çÇÁ¸¦ ÇÇÇϱâ À§ÇØ ÀÌ Ç÷¡±×¸¦ »ç¿ëÇÒ °ÍÀÌ´Ù.

±×¸² 2. ÆÛÁñ Á¶°¢°ú ¼¿

Listing 2. Cell Ŭ·¡½º

public class Cell {
  public static final int NUMBEROFSIDES = 6;

  // The sides of a cell
  public static final int EAST      = 0;
  public static final int SOUTHEAST = 1;
  public static final int SOUTHWEST = 2;
  public static final int WEST      = 3;
  public static final int NORTHWEST = 4;
  public static final int NORTHEAST = 5;

  private Cell[] neighbours = new Cell[NUMBEROFSIDES];

  private boolean processed = false;

  public Cell getNeighbour(int side) {
    return neighbours[side];
  }

  public void setNeighbour(int side, Cell cell) {
    neighbours[side] = cell;
  }

  public boolean isProcessed() {
    return processed;
  }

  public void setProcessed(boolean b) {
    processed = b;
  }
}

Piece Ŭ·¡½º´Â Á¶±Ý ´õ Àç¹ÌÀÖ´Ù. PieceÀÇ ¼ø¿­À» °è»êÇϱâ À§Çؼ­´Â ¸Þ¼Òµå°¡ ÇÊ¿äÇϱ⠶§¹®ÀÌ´Ù. ¼¿ÀÇ ¿©¼¸ º¯ ÁÖÀ§¿¡¼­ Á¶°¢À» ȸÀü½ÃÅ°°í, À̸¦ ¾ÕµÚ·Î µÚÁýÀ¸¸ç ¸¶Áö¸·À¸·Î ¼¿ÀÇ ¿©¼¸ º¯ Áß ÇÑ º¯ ÁÖÀ§¿¡ À̸¦ ´Ù½Ã ȸÀü½ÃÅ°¸é¼­ ¸ðµç ¼ø¿­µéÀ» ãÀ» ¼ö ÀÖ´Ù. ¾Õ¼­ ¾ð±ÞÇßµíÀÌ, Á¶°¢Àº ´Ù ¼¸ °³ÀÇ ÀÎÁ¢ ¼¿µé·Î ±¸¼ºµÇ¾î ÀÖ´Ù. Á¶°¢À» µÚÁý°Å³ª ȸÀü½ÃÅ°´Â °ÍÀº ÀÌ°ÍÀÇ ¸ðµç ¼¿µéÀ» µÚÁý°Å³ª ȸÀü½ÃÅ°´Â °ÍÀÌ´Ù. µû¶ó¼­ Cell °´Ã¼¸¦ À§ÇØ flip()°ú rotate() ¸Þ¼Òµå°¡ ÇÊ¿äÇÏ´Ù. µÚÁý±â¿Í ȸÀü ¸ðµÎ ÀÌ¿ôÇÏ´Â º¯À» º¯È­½ÃÅ´À¸·Î¼­ ½±°Ô ¼öÇàÇÒ ¼ö ÀÖ´Ù. ÀÌ·¯ÇÑ ¸Þ¼ÒµåµéÀº Cell Ŭ·¡½ºÀÇ PieceCell ÇÏÀ§ Ŭ·¡½º¿¡¼­ Á¦°øµÈ´Ù. (Listing 3). PieceCell °´Ã¼´Â Piece °´Ã¼¿¡¼­ »ç¿ëµÇ´Â ¼¿ÀÌ´Ù.

Listing 3. PieceCell ÇÏÀ§Å¬·¡½º

public class PieceCell extends Cell {
  public void flip() {
    Cell buffer = getNeighbour(NORTHEAST);
    setNeighbour(NORTHEAST, getNeighbour(NORTHWEST));
    setNeighbour(NORTHWEST, buffer);
    buffer = getNeighbour(EAST);
    setNeighbour(EAST, getNeighbour(WEST));
    setNeighbour(WEST, buffer);
    buffer = getNeighbour(SOUTHEAST);
    setNeighbour(SOUTHEAST, getNeighbour(SOUTHWEST));
    setNeighbour(SOUTHWEST, buffer);
  }

  public void rotate() {
    // Clockwise rotation
    Cell eastNeighbour = getNeighbour(EAST);
    setNeighbour(EAST, getNeighbour(NORTHEAST));
    setNeighbour(NORTHEAST, getNeighbour(NORTHWEST));
    setNeighbour(NORTHWEST, getNeighbour(WEST));
    setNeighbour(WEST, getNeighbour(SOUTHWEST));
    setNeighbour(SOUTHWEST, getNeighbour(SOUTHEAST));
    setNeighbour(SOUTHEAST, eastNeighbour);
  }
}

PieceCell Ŭ·¡½º¸¦ »ç¿ëÇÏ¿©, Piece Ŭ·¡½º ±¸ÇöÀ» ¿Ï¼ºÇÒ ¼ö ÀÖ´Ù. Listing 4´Â ¼Ò½º ÄÚµåÀÌ´Ù:

Listing 4. Piece Ŭ·¡½º

public class Piece {
  public static final int NUMBEROFCELLS = 5;
  public static final int NUMBEROFPERMUTATIONS = 12;

  private PieceCell[] pieceCells = new PieceCell[NUMBEROFCELLS];
  private int currentPermutation = 0;

  private void rotatePiece() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      pieceCells[i].rotate();
    }
  }

  private void flipPiece() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      pieceCells[i].flip();
    }
  }

  public Piece nextPermutation() {
    if (currentPermutation == NUMBEROFPERMUTATIONS)
      currentPermutation = 0;

    switch (currentPermutation%6) {
      case 0:
        // Flip after every 6 rotations
        flipPiece();
        break;

      default:
        rotatePiece();
        break;
    }

    currentPermutation++;

    return this;
  }

  public void resetProcessed() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      pieceCells[i].setProcessed(false);
    }
  }

  //Getters and setters have been omitted
}

Board Ŭ·¡½º
Board Ŭ·¡½º¸¦ ±¸ÇöÇϱâ Àü¿¡, µÎ °¡Áö Àç¹ÌÀÖ´Â ¹®Á¦¸¦ ¤°í ³Ñ¾î°¡ÀÚ. ¿ì¼±, µ¥ÀÌÅÍ ±¸Á¶¿¡ ´ëÇØ °áÁ¤ÇØ¾ß ÇÑ´Ù. Meteor ÆÛÁñ º¸µå´Â ±âº»ÀûÀ¸·Î Á¤À°°¢ÀÇ 5x10 ±×¸®µåÀÌ´Ù. 50 Cell °´Ã¼ ¾î·¹À̷μ­ Ç¥ÇöÇÒ ¼ö ÀÖ´Ù. Cell Ŭ·¡½º¸¦ Á÷Á¢ »ç¿ëÇÏ´Â ´ë½Å BoardCell ÇÏÀ§Å¬·¡½º¸¦ »ç¿ëÇÒ °ÍÀÌ´Ù.(Listing 5). ¼¿À» Â÷ÁöÇÏ°í ÀÖ´Â Á¶°¢À» Æ®·¡Å·ÇÒ ¼ö ÀÖ´Ù:

Listing 5. BoardCell ÇÏÀ§Å¬·¡½º

public class BoardCell extends Cell {
  private Piece piece = null;

  public Piece getPiece() {
    return piece;
  }

  public void setPiece(Piece piece) {
    this.piece = piece;
  }
}

ÇÑ ¾î·¹ÀÌ¿¡ 50°³ÀÇ ¸ðµç º¸µå ¼¿À» ÀúÀåÇÏ·Á¸é ¾à°£ ÀåȲÇÑ ÃʱâÈ­ Äڵ带 ÀÛ¼ºÇØ¾ß ÇÑ´Ù. ÃʱâÈ­´Â º¸µåÀÇ °¢ ¼¿¿¡ ´ëÇÑ ÀÎÁ¢ º¸µå ¼¿À» ±¸ºÐÇÏ´Â °ÍÀÌ´Ù. (±×¸² 3). cell 0Àº µÎ°³ÀÇ ÀÌ¿ôÀ» °®°í ÀÖ´Ù: µ¿ÂÊÀÇ cell 1°ú ³²µ¿ÂÊÀÇ cell 5. Listing 6 Àº initializeBoardCell()¸Þ¼Òµå·Î¼­ Board Ŭ·¡½ºÀÇ »ý¼ºÀÚ¿¡¼­ È£ÃâµÇ¾î ÃʱâÈ­¸¦ ¼öÇàÇÑ´Ù.

±×¸² 3. ¼¿ ¾î·¹À̷ΠǥÇöµÈ º¸µå

º¸µå¿ë µ¥ÀÌÅÍ ±¸Á¶¸¦ ±¸ÇöÇß´Ù¸é ´ÙÀ½ ¹®Á¦·Î ¿Å°Ü°¡º¸ÀÚ: º¸µå¿¡ Á¶°¢À» ³õ´Â ¸Þ¼ÒµåÀÎ placePiece()¸¦ ÀÛ¼ºÇÏ´Â °ÍÀÌ´Ù. ÀÌ ¸Þ¼Òµå¸¦ ÀÛ¼ºÇÏ´Â µ¥ ÀÖ¾î °¡Àå ¾î·Á¿î ºÎºÐÀº Á¶°¢ÀÌ ±âÁ¸ À§Ä¡¿¡¼­ º¸µå¿Í ¸Â´ÂÁöÀÇ ¿©ºÎ¸¦ °áÁ¤ÇÏ´Â °ÍÀÌ´Ù. Á¶°¢ÀÌ ¸Â´ÂÁö ¿©ºÎ¸¦ °áÁ¤ÇÏ´Â ÇÑ °¡Áö ¹æ¹ýÀº ±×°ÍÀÌ º¸µå¿¡ ³õ¿©Á® ÀÖ´Ù¸é Á¶°¢ÀÇ ¼¿¿¡ ÀÇÇØ Á¡À¯µÈ ¸ðµç º¸µå ¼¿À» ã´Â °ÍÀÌ´Ù. ÀÌ·¯ÇÑ º¸µå ¼¿µéÀ» °®´Â´Ù¸é ½±°Ô »õ·Î¿î Á¶°¢ÀÌ ¸Â´ÂÁö¸¦ ½±°Ô °áÁ¤ÇÒ ¼ö ÀÖ´Ù. ¸ðµç »óÀÀÇÏ´Â º¸µå ¼¿µéÀº ºñ¿öÀÖ¾î¾ß Çϸç Á¶°¢Àº º¸µå¿¡ ¿Ïº®ÇÏ°Ô ¸Â¾Æ¾ß ÇÑ´Ù. ÀÌ ÇÁ·Î¼¼½º´Â findOccupiedBoardCells() ¸Þ¼Òµå¿Í placePiece() ¸Þ¼Òµå·Î ±¸ÇöµÈ´Ù. (Listing 6). PieceCell °´Ã¼ÀÇ processed Çʵ带 »ç¿ëÇÏ¿© findOccupiedBoardCells() ¸Þ¼ÒµåÀÇ ¹«ÇÑ Àç±Í(recursion)¸¦ ÇÇÇÑ´Ù´Â °Í¿¡ ÁÖ¸ñÇÏÀÚ.

Listing 6. Board Ŭ·¡½º

public class Board {
  public static final int NUMBEROFCELLS = 50;
  public static final int NUMBEROFCELLSINROW = 5;

  private BoardCell[] boardCells = new BoardCell[NUMBEROFCELLS];

  public Board() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      boardCells[i] = new BoardCell();
    }

    for (int i = 0; i < NUMBEROFCELLS; i++) {
      initializeBoardCell(boardCells[i], i);
    }
  }

  /**
   * Initialize the neighbours of the given boardCell at the given
   * index on the board
   */
  private void initializeBoardCell(BoardCell boardCell, int index) {
    int row = index/NUMBEROFCELLSINROW;

    // Check if cell is in last or first column
    boolean isFirst = (index%NUMBEROFCELLSINROW == 0);
    boolean isLast = ((index+1)%NUMBEROFCELLSINROW == 0);

    if (row%2 == 0) { // Even rows
      if (row != 0) {
        // Northern neighbours
        if (!isFirst) {
          boardCell.setNeighbour(Cell.NORTHWEST, boardCells[index-6]);
        }
        boardCell.setNeighbour(Cell.NORTHEAST, boardCells[index-5]);
      }
      if (row != ((NUMBEROFCELLS/NUMBEROFCELLSINROW)-1)) {
        // Southern neighbours
        if (!isFirst) {
          boardCell.setNeighbour(Cell.SOUTHWEST, boardCells[index+4]);
        }
        boardCell.setNeighbour(Cell.SOUTHEAST, boardCells[index+5]);
      }
    }
    else { // Uneven rows
      // Northern neighbours
      if (!isLast) {
        boardCell.setNeighbour(Cell.NORTHEAST, boardCells[index-4]);
      }
      boardCell.setNeighbour(Cell.NORTHWEST, boardCells[index-5]);
      // Southern neighbours
      if (row != ((NUMBEROFCELLS/NUMBEROFCELLSINROW)-1)) {
        if (!isLast) {
          boardCell.setNeighbour(Cell.SOUTHEAST, boardCells[index+6]);
        }
        boardCell.setNeighbour(Cell.SOUTHWEST, boardCells[index+5]);
      }
    }

    // Set the east and west neighbours
    if (!isFirst) {
      boardCell.setNeighbour(Cell.WEST, boardCells[index-1]);
    }
    if (!isLast) {
      boardCell.setNeighbour(Cell.EAST, boardCells[index+1]);
    }
  }

  public void findOccupiedBoardCells(
    ArrayList occupiedCells, PieceCell pieceCell, BoardCell boardCell) {
    if (pieceCell != null && boardCell != null && !pieceCell.isProcessed()) {
      occupiedCells.add(boardCell);
      
      /* Neighbouring cells can form loops, which would lead to an
         infinite recursion. Avoid this by marking the processed 
         cells. */
      
      pieceCell.setProcessed(true);

      // Repeat for each neighbour of the piece cell
      for (int i = 0; i < Cell.NUMBEROFSIDES; i++) {
        findOccupiedBoardCells(occupiedCells,
                               (PieceCell)pieceCell.getNeighbour(i),
                               (BoardCell)boardCell.getNeighbour(i));
      }
    }
  }

  public boolean placePiece(Piece piece, int boardCellIdx) {
    // We will manipulate the piece using its first cell
    return placePiece(piece, 0, boardCellIdx);
  }

  public boolean 
    placePiece(Piece piece, int pieceCellIdx, int boardCellIdx) {
    // We're going to process the piece
    piece.resetProcessed();

    // Get all the boardCells that this piece would occupy
    ArrayList occupiedBoardCells = new ArrayList();
    findOccupiedBoardCells(occupiedBoardCells,
                           piece.getPieceCell(pieceCellIdx),
                           boardCells[boardCellIdx]);

    if (occupiedBoardCells.size() != Piece.NUMBEROFCELLS) {
      // Some cells of the piece don't fall on the board
      return false;
    }

    for (int i = 0; i < occupiedBoardCells.size(); i++) {
      if (((BoardCell)occupiedBoardCells.get(i)).getPiece() != null)
        // The board cell is already occupied by another piece
        return false;
    }

    // Occupy the board cells with the piece
    for (int i = 0; i < occupiedBoardCells.size(); i++) {
      ((BoardCell)occupiedBoardCells.get(i)).setPiece(piece);
    }

    return true; // The piece fits on the board
  }

  public void removePiece(Piece piece) {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      // Piece objects are unique, so use reference equality
      if (boardCells[i].getPiece() == piece) {
        boardCells[i].setPiece(null);
      }
    }
  }
}

ÀÌ°ÍÀ¸·Î ù ¹ø° ¼Ö·ç¼Ç ±¸ÇöÀÌ ¿Ï¼ºµÇ¾ú´Ù. ÀÌÁ¦ Å×½ºÆ® Çغ¸ÀÚ.

ÇÁ·Î±×·¥ ½ÇÇàÇϱâ
ù ¹ø° ÆÛÁñ ÇØ°á ÇÁ·Î±×·¥À» ³¡¸¶ÃÆÀ¸´Ï Meteor ÆÛÁñ¿¡ ´ëÇÑ ¸ðµç °¡´ÉÇÑ ¼Ö·ç¼ÇÀ» ãÀ» ¼ö ÀÖ´Ù. ÀÌÀü ¼½¼Ç¿¡¼­ ¼³¸íÇÑ ¼Ò½º ÄÚµå´Â ¼Ò½º ´Ù¿î·ÎµåÀÇ meteor.initial ÆÐÅ°Áö¿¡ ÀÖ´Ù. ÀÌ ÆÐÅ°Áö´Â ÇÁ·Î±×·¥À» ½ÃÀÛÇÏ´Â solve() ¸Þ¼Òµå¿Í main() ¸Þ¼Òµå°¡ ÀÖ´Â Solver Ŭ·¡½º¸¦ Æ÷ÇÔÇÏ°í ÀÖ´Ù. Solver Ŭ·¡½ºÀÇ »ý¼ºÀÚ´Â ¸ðµç ÆÛÁñ Á¶°¢µéÀ» ÃʱâÈ­ÇÏ°í ±×µéÀ» pieceList¿¡ Ãß°¡ÇÑ´Ù. java meteor.initial.Solver¸¦ »ç¿ëÇÏ¿© ÇÁ·Î±×·¥À» ½ÃÀÛÇÒ ¼ö ÀÖ´Ù.

ÀÌ ÇÁ·Î±×·¥Àº ¼Ö·ç¼ÇÀ» ã±â ½ÃÀÛÇÑ´Ù. ÇÏÁö¸¸ ¿©·¯ºÐµµ º¸µíÀÌ ¾Æ¹«°Íµµ ¸ø ã´Â´Ù. ½ÇÁ¦·Î ÀÌ°ÍÀº ¸ðµç °¡´ÉÇÑ ¼Ö·ç¼ÇÀ» ã±â´Â ÇÏÁö¸¸ ´ë½Å Àγ»½ÉÀ» °¡Á®¾ßÇÑ´Ù. ´Ü ÇϳªÀÇ ¼Ö·ç¼ÇÀ» ã´Âµ¥ ¸¹Àº ½Ã°£ÀÌ °É¸°´Ù. ¿ì¸®ÀÇ Å×½ºÆ® ÄÄÇ»ÅÍÀÎ RedHat Linux 7.2¿Í Java 1.4.0À» ±¸µ¿ÇÏ´Â Athlon XP 1500+(512MB RAM)´Â 8 ½Ã°£ ÈÄ¿¡ ù ¹ø° ¼Ö·ç¼ÇÀ» ã¾Ò´Ù. ¸ðµç ¼Ö·ç¼ÇÀ» ãÀ¸·Á¸é ¼ö °³¿ùÀÌ °É¸±Áöµµ ¸ð¸¥´Ù.

ºÐ¸íÈ÷ ÆÛÆ÷¸Õ½º ¹®Á¦°¡ ÀÖ´Ù. ÃÖÀûÈ­¸¦ À§ÇÑ Ã¹ ¹ø° È帴 ÆÛÁñ Ç®ÀÌ ¾Ë°í¸®ÁòÀÌ´Ù. ¿ì¸®´Â ÇöÀç ¸ðµç °¡´ÉÇÑ ¼Ö·ç¼ÇÀ» ã´Âµ¥ ¼øÁøÇÏ°í ¹«½ÄÇÑ Á¢±Ù¹æ½ÄÀ» »ç¿ëÇÏ°í ÀÖ´Ù. ÀÌ ¾Ë°í¸®ÁòÀ» Æ©´×ÇØ¾ß ÇÑ´Ù. ¿ì¸®°¡ ÇÒ ¼ö ÀÖ´Â µÎ ¹ø° ÀÏÀº Àӽà µ¥ÀÌÅ͸¦ ij½ÌÇÏ´Â °ÍÀÌ´Ù. ¿¹¸¦ µé¾î ¸Å¹ø Á¶°¢ÀÇ ¼ø¿­À» Àç°è»ê ÇÏ´Â ´ë½Å¿¡ ±×·¯ÇÑ ¼ø¿­À» ij½ÌÇÏ´Â °ÍÀÌ´Ù. ¸¶Áö¸·À¸·Î ¸î °¡Áö Àú¼öÁØ ÃÖÀûÈ­ ±â¼ú, ¿¹¸¦µé¾î ºÒÇÊ¿äÇÑ ¸Þ¼Òµå È£ÃâÀ» ÇÇÇÏ´Â ½ÄÀÇ Àú¼öÁØ ±â¼úÀ» Àû¿ëÇÏ´Â °ÍÀÌ´Ù. ´ÙÀ½ ¼½¼Ç¿¡¼­ Àú ¼öÁØ ÃÖÀûÈ­ ±â¼úÀ» ¿¬±¸ÇÏ°Ú´Ù.

¾Ë°í¸®Áò Çâ»ó½ÃÅ°±â
Listing 1À» ´Ù½Ã º¸¸é¼­ óÀ½ÀÇ ÆÛÁñ Ç®ÀÌ ¾Ë°í¸®ÁòÀ» ¾î¶»°Ô ÃÖÀûÈ­ÇÒ ¼ö ÀÖ´ÂÁö¸¦ »ý°¢Çغ¸ÀÚ. ¾Ë°í¸®ÁòÀ» ÃÖÀûÈ­ÇÏ´Â ÁÁÀº ¹æ¹ýÀº À̸¦ ½Ã°¢È­ÇÏ´Â °ÍÀÌ´Ù. ½Ã°¢È­´Â ±¸ÇöµÇ°íÀÖ´Â ÇÁ·Î¼¼½ºÀÇ ÀÌÇظ¦ µ½´Â´Ù. ´ÙÀ½ ¼½¼Ç¿¡¼­´Â µÎ °¡Áö ºñÈ¿À²¼º¿¡ ´ëÇØ À̾߱âÇÏ°Ú´Ù.

¼¶ ŽÁö(Island detection) pruning
Listing 1ÀÇ ¾Ë°í¸®ÁòÀº Á¶°¢À» º¸µåÀÇ ¸ðµç À§Ä¡¿¡ ¸ÂÃá´Ù. ±×¸² 4´Â ÇÁ·Î¼¼½ºÀÇ Ã³À½¿¡ ÀÖ´Â °¡´ÉÇÑ º¸µå »óȲÀ» º¸¿©ÁØ´Ù. Ǫ¸¥ Á¶°¢ÀÇ ÇöÀç ¼ø¿­Àº ù ¹ø° °¡´ÉÇÑ º¸µå¿¡ ÀÖ°í ³ë¶õ»ö Á¶°¢ÀÇ ÇöÀç ¼ø¿­Àº µÎ ¹ø° °¡´ÉÇÑ º¸µå À§Ä¡·Î À̵¿Çß´Ù. ±×·±´ÙÀ½ ¼¼ ¹ø° Á¶°¢À¸·Î À̾îÁø´Ù. ÇÏÁö¸¸ ±×¸² 4¸¦ ÀÚ¼¼È÷ º¸¸é ÀÌ·¯ÇÑ À§Ä¡¿¡¼­´Â Ǫ¸¥»ö°ú ³ë¶õ»öÀ» °¡Áø ÆÛÁñ¿¡´Â °¡´ÉÇÑ ¼Ö·ç¼ÇÀÌ ¾ø´Ù´Â °ÍÀÌ ¸í¹éÇØÁø´Ù. ÀÌÀ¯´Â ±×·¯ÇÑ µÎ Á¶°¢Àº ÀÌ¿ôÇÏ´Â ºó ¼¿ÀÇ ¼¶(island)À» Çü¼ºÇ߱⠶§¹®ÀÌ´Ù. ¸ðµç ÆÛÁñ Á¶°¢Àº ´Ù¼¸°³ÀÇ ¼¿·Î ±¸¼ºµÇ¾îÀֱ⠶§¹®¿¡ ÀÌ·¯ÇÑ ¼¶À» ä¿ï ¹æ¹ýÀÌ ¾ø´Ù. º¸µå¿¡ ³²¾ÆÀÖ´Â ¿©´ü°³ÀÇ Á¶°¢µéÀ» ¸ÂÃß·Á´Â ¸ðµç ³ë·ÂÀº ¹«ÀǹÌÇÏ´Ù. ÇÊ¿äÇÑ °ÍÀº ä¿öÁú ¼ö ¾ø´Â º¸µå¿¡¼­ ¼¶À» ¹ß°ßÇß´Ù¸é ¾Ë°í¸®ÁòÀ» ³¡³»´Â °ÍÀÌ´Ù.

±×¸²4. º¸µåÀÇ ¼¶(island)

¿©±â¿¡¼­ Àç±Í °Ë»ö ¾Ë°í¸®ÁòÀ» ¸·´Â ÀÌ·¯ÇÑ ÇÁ·Î¼¼½º¸¦ pruningÀ̶ó°í ÇÏ°Ú´Ù. pruning ÇÔ¼ö¸¦ Solver Ŭ·¡½º¿¡ Ãß°¡ÇÏ´Â °ÍÀº ½±´Ù. solve() ¸Þ¼Òµå¿¡ ¸ðµç Àç±Í È£ÃâÀ» Çϱâ Àü¿¡ º¸µå »óÀÇ ¼¶À» Á¡°ËÇÑ´Ù. 5ÀÇ ¹è¼ö°¡ ¾Æ´Ñ ¸¹Àº ºó ¼¿µé·Î ±¸¼ºµÇ¾îÀÖ´Â ¼¶ÀÌ ÀÖ´Ù¸é Àç±Í È£ÃâÀ» ÇÏÁö ¾Ê´Â´Ù. ´ë½Å ¾Ë°í¸®ÁòÀº ÇöÀç ·¹º§ÀÇ Àç±Í·Î °è¼ÓµÈ´Ù. Listing 7°ú 8Àº ÇʼöÀûÀÎ ÄÚµå Á¶Á¤À» º¸¿©ÁÖ°í ÀÖ´Ù:

Listing 7. pruningÀ» ÀÌ¿ëÇÑ ÆÛÁñ Ç®ÀÌ ¾Ë°í¸®Áò

public class Solver {
  public void solve() {
    ...
            if (!prune()) solve();
    ...
  }

  private boolean prune() {
    /* We'll use the processed field of board cells to avoid 
    infinite loops */
    board.resetProcessed();

    for (int i = 0; i < Board.NUMBEROFCELLS; i++) {
      if (board.getBoardCell(i).getIslandSize()%Piece.NUMBEROFCELLS != 0) {
        // We have found an unsolvable island
        return true;
      }
    }

    return false;
  }
}

Listing 8. getIslandSize() ¸Þ¼Òµå

public class BoardCell {
  public int getIslandSize() {
    if (!isProcessed() && isEmpty()) {
      setProcessed(true); // Avoid infinite recursion
      int numberOfCellsInIsland = 1; // this cell 

      for (int i = 0; i < Cell.NUMBEROFSIDES; i++) {
        BoardCell neighbour=(BoardCell)getNeighbour(i);
        if (neighbour != null) {
          numberOfCellsInIsland += neighbour.getIslandSize();
        }
      }
      return numberOfCellsInIsland;
    }
    else {
      return 0;
    }
  }
}

ä¿ì±â(fill-up) ¾Ë°í¸®Áò
óÀ½ ¾Ë°í¸®ÁòÀÇ µÎ ¹ø° ´ÜÁ¡Àº ÀÌ°ÍÀÌ ±âº»ÀûÀ¸·Î ¸¹Àº ¼¶µéÀ» ¸¸µé¾î³½´Ù´Â °ÍÀÌ´Ù. ÀÌ°ÍÀº ¿ì¸®°¡ ÇÑ Á¶°¢¿¡¼­ ÇϳªÀÇ ¼ø¿­À» ÃëÇØ ±× Á¶°¢ÀÇ ´ÙÀ½ ¼ø¿­·Î º¯È¯Çϱâ Àü¿¡ º¸µå·Î À̵¿½ÃÅ°±â ¶§¹®ÀÌ´Ù. ¿¹¸¦ µé¾î, ±×¸² 5¿¡¼­ Ǫ¸¥ Á¶°¢ÀÇ ÇöÀç ¼ø¿­À» ¼¼ ¹ø° °¡´ÉÇÑ º¸µå À§Ä¡·Î À̵¿½ÃÄ×´Ù. º¸´Ù½ÃÇÇ ÀÌ°ÍÀº º¸µåÀÇ »ó´Ü¿¡ ¼¶À» ¸¸µé¾î³½´Ù. ÀÌÀü ¼½¼Ç¿¡¼­ Ãß°¡ÇÑ ¾ÆÀÏ·£µå ŽÁö pruningÀÌ ¿ì¸®°¡ ¸¸µé¾î³½ ¸¹Àº ¼¶µé ¶§¹®¿¡ ³î¶ó¿î ÆÛÆ÷¸Õ½º Çâ»óÀ» °¡Á®¿ÀÁö¸¸ ù ¹ø° Àå¼Ò¿¡¼­ ¸¸µç ¼¶ÀÇ ¼ö¸¦ ÃÖ¼ÒÈ­ÇÏ´Â ¾Ë°í¸®ÁòÀ» ¾÷µ¥ÀÌÆ® ÇÒ ¼ö ÀÖ´Ù¸é ÁÁÀ» °ÍÀÌ´Ù.

±×¸² 5. ¼¶ ¸¸µé±â

¿ì¸®°¡ ¸¸µç ¼¶ÀÇ ¼ö¸¦ ÁÙÀ̱âÀ§Çؼ­ ¾Ë°í¸®ÁòÀÌ ºñ¾îÀÖ´Â º¸µå À§Ä¡¿¡ ÁýÁߵǾîÀÖ´Ù¸é ÃÖ»óÀÌ´Ù. µû¶ó¼­ º¸µå¸¦ ä¿ì±â À§ÇØ ¸ðµç °¡´ÉÇÑ ¹æ¹ýÀ» ½ÃµµÇÏ´Â ´ë½Å º¸µå¸¦ ¿ÞÂÊ¿¡¼­ ¿À¸¥ÂÊÀ¸·Î À§¿¡¼­ ¾Æ·¡·Î ä¿ö°£´Ù. ÀÌ »õ·Î¿î ÆÛÁñ Ç®ÀÌ ¾Ë°í¸®ÁòÀº Listing 9¿¡ ³ªÅ¸³ªÀÖ´Ù:

Listing 9. ä¿ì±â ¹æ½ÄÀÇ ÆÛÁñ Ç®ÀÌ ¾Ë°í¸®Áò

public void solve() {
  if (!pieceList.isEmpty()) {
    // We'll try to find a piece that fits on this board cell
    int emptyBoardCellIdx = board.getFirstEmptyBoardCellIndex();

    // Try all available pieces
    for (int h = 0; h < pieceList.size(); h++) {
      Piece currentPiece = (Piece)pieceList.remove(h);

      for (int i = 0; i < Piece.NUMBEROFPERMUTATIONS; i++) {
        Piece permutation = currentPiece.nextPermutation();
        
        /* Instead of always using the first cell to manipulate
           the piece, we now try to fit any cell of the piece on 
           the first empty board cell */
        
        for (int j = 0; j < Piece.NUMBEROFCELLS; j++) {
          if (board.placePiece(permutation, j, emptyBoardCellIdx)) {
            if (!prune()) solve();
            board.removePiece(permutation);
          }
        }
      }

      
      /* Put the piece back into the list at the position where
         we took it to maintain the order of the list */
      
      pieceList.add(h, currentPiece);
    }
  }
  else {
    puzzleSolved();
  }
}

¿ì¸®ÀÇ »õ·Î¿î Á¢±Ù ¹æ½ÄÀº ¸ðµç °¡´ÉÇÑ Á¶°¢À» ù ¹ø° ºó º¸µå ¼¿¿¡ ¸ÂÃß±â À§ÇÔÀÌ´Ù. ÀÌ¿ëÇÒ ¼ö ÀÖ´Â ¸ðµç Á¶°¢ÀÇ ¸ðµç °¡´ÉÇÑ ¼ø¿­À» ½ÃµµÇÏ´Â °Í¸¸À¸·Î´Â ÃæºÐÇÏÁö ¾Ê´Ù. ¿ì¸®´Â ¶ÇÇÑ Á¶°¢ÀÇ ¾î¶² Á¶°¢ ¼¿À» °¡Áö°í ºñ¾îÀÖ´Â º¸µå ¼¿À» ä¿ö¾ßÇÑ´Ù. ù ¾Ë°í¸®Áò¿¡¼­ ¿ì¸®´Â ÀÌ Ã¹ ¹ø° ¼¿À» »ç¿ëÇÏ¿© Á¶°¢À» Á¶ÀÛÇÑ´Ù°í °¡Á¤Çß´Ù. ÀÌÁ¦´Â ±×¸² 6 ó·³ ±× Á¶°¢¿¡ ¸ðµç ¼¿À» ½ÃµµÇØ¾ß ÇÑ´Ù. ÇÎÅ©»ö Á¶°¢ÀÇ ÇöÀç ¼ø¿­Àº º¸µå À§Ä¡ 5¿¡ À妽º 0À¸·Î Á¶°¢ ¼¿À» ³õÀ» ¶§ º¸µå¿¡ ¸ÂÁö ¾Ê´Â´Ù. ÇÏÁö¸¸ µÎ ¹ø° Á¶°¢ ¼¿À» »ç¿ëÇÒ ¶§ ¸Â´Â´Ù.

±×¸² 6. Á¶°¢ ¼¿

¾÷µ¥ÀÌÆ® ÇÁ·Î±×·¥ ½ÇÇàÇϱâ
ù ÇÁ·Î±×·¥À» ½ÇÇàÇϸ鼭 ¿À·£ ½Ã°£µ¿¾È ¼Ö·ç¼ÇÀ» ãÁö ¸øÇß´Ù. ÀÌÁ¦ Çâ»óµÈ ¾Ë°í¸®Áò°ú ¼¶ ŽÁö(island-detection) pruningÀ¸·Î ´Ù½Ã ½ÃµµÇغ¸ÀÚ. ÀÌ ÇÁ·Î±×·¥ ¹öÀü ÄÚµå´Â meteor.algorithm ÆÐÅ°Áö¿¡ ÀÖ´Ù. java meteor.algorithm.Solver¸¦ »ç¿ëÇÏ¸é °©Àڱ⠼ַç¼ÇÀÌ ¶°¿À¸£´Â °ÍÀ» °æÇèÇÏ°Ô µÈ´Ù. Å×½ºÆ® ÄÄÇ»ÅÍ´Â 157ÃÊ ¸¸¿¡ 2,098°³ÀÇ °¡´ÉÇÑ ¼Ö·ç¼ÇÀ» °è»êÇÑ´Ù. ±²ÀåÇÑ ÆÛÆ÷¸Õ½º Çâ»óÀ» ÀÌ·èÇß´Ù. ¼Ö·ç¼Ç ´ç ¼ö ½Ã°£¿¡¼­ ÃÖ¼Ò 0.1ÃÊ·Î ³·¾ÆÁø°ÍÀÌ´Ù. ´ë·« 400,000 ¹è »¡¶óÁ³´Ù. ¼¶ ŽÁö pruningÀ¸·Î Á¶ÇÕµÈ Ã³À½ ¾Ë°í¸®ÁòÀº 6,363 ÃÊ ¾È¿¡ ¿Ï¼ºÇß´Ù. pruning ÃÖÀûÈ­´Â 10,000 ¹èÀÇ ¼ÓµµÇâ»óÀ» °¡Á®¿À°í ä¿ì±â ¾Ë°í¸®ÁòÀº Ãß°¡·Î 40¹èÀÇ ¼ÓµµÇâ»óÀ» °¡Á®¿Â´Ù.

Áß°£ °á°ú ij½ÌÇϱâ
ÆÛÁñ Ç®ÀÌ ¾Ë°í¸®ÁòÀ» Àç¼³°è ÇÔÀ¸·Î¼­ ÇÁ·Î±×·¥ÀÇ ½ÇÇà ¼Óµµ¸¦ Å©°Ô Çâ»ó½ÃÄ×´Ù. ÃÖÀûÈ­¸¦ ´õ¿í ÁøÇà½ÃÅ°±â À§Çؼ­ ±â¼úÀû ÆÛÆ÷¸Õ½º ±â¼úÀ» »ìÆ캸ÀÚ. ÀÚ¹Ù ÇÁ·Î±×·¥¿¡¼­ °í·ÁÇØ¾ß ÇÏ´Â Áß¿äÇÑ ¹®Á¦´Â °¡ºñÁö Ä÷º¼Ç(garbage collection)ÀÌ´Ù. -verbose:gc ¸í·ÉÇà ½ºÀ§Ä¡¸¦ »ç¿ëÇÏ¿© ÇÁ·Î±×·¥ÀÌ ½ÇÇàµÇ´Â µ¿¾È °¡ºñÁö Ä÷ºÅÍÀÇ ÀÛµ¿À» º¸¿©ÁÙ ¼ö ÀÖ´Ù.

java -verbose:gc meteor.algorithm.Solver

ÀÌ ½ºÀ§Ä¡·Î ÇÁ·Î±×·¥À» ½ÇÇàÇÏ¸é °¡ºñÁö Ä÷ºÅÍ¿¡¼­ ¸¹Àº ¾Æ¿ôDz(ourput)À» ¾ò´Â´Ù. ¼Ò½º Äڵ带 ºÐ¼®Çغ¸¸é ¹®Á¦´Â Board Ŭ·¡½ºÀÇ placePiece() ¸Þ¼Òµå¿¡ ÀÖ´Â ArrayList ¸®½ºÆ® Àӽà °´Ã¼ÀÇ ÃʱâÈ­ÀÌ´Ù. (Listing 6) ÇÑ Á¶°¢ÀÇ Æ¯Á¤ ¼ø¿­ÀÌ Ã¤¿öÁú º¸µå ¼¿À» °®±âÀ§Çؼ­´Â ArrayList °´Ã¼¸¦ »ç¿ëÇÑ´Ù. ÀÌ ¸®½ºÆ®¸¦ ¸Å¹ø °è»êÇÏ´Â ´ë½Å, ´ÙÀ½ ·¹ÆÛ·±½º¸¦ À§ÇØ ÀÌ °á°ú¸¦ ij½ÌÇÏ´Â °ÍÀÌ ³´´Ù.

findOccupiedBoardCells() ¸Þ¼Òµå´Â ±× Á¶°¢ÀÇ Æ¯Á¤ ¼¿ÀÌ Æ¯Á¤ º¸µå À§Ä¡¿¡ ³õÀ̰ԵǸé ÆÛÁñ Á¶°¢À¸·Î ä¿öÁø ÆÛÁñ º¸µåÀÇ ¼¿À» °áÁ¤ÇÑ´Ù. ¸Þ¼ÒµåÀÇ °á°ú´Â ¼¼ °³ÀÇ ¸Å°³º¯¼ö¿¡ ÀÇÇØ °áÁ¤µÈ´Ù. ù° ÆÛÁñ Á¶°¢ ¶Ç´Â ±×°ÍÀÇ ¼ø¿­À» °®°í ÀÖ´Ù. µÑ°, Á¶°¢À» Á¶ÀÛÇϴµ¥ »ç¿ëÇÏ´Â Á¶°¢ÀÇ ¼¿ÀÌ ÀÖ´Ù. ¸¶Áö¸·À¸·Î Á¶°¢µéÀ» ³õÀ» º¸µåÀÇ ¼¿À» °®°í ÀÖ´Ù. ÀÌ °á°ú¸¦ ij½ÌÇϱâÀ§Çؼ­ Å×À̺íÀ» ¸ðµç °¡´ÉÇÑ Á¶°¢ ¼ø¿­·Î ¿¬°áÇÑ´Ù. ÀÌ Å×À̺íÀº ÁöÁ¤µÈ Á¶°¢ ¼¿ À妽º¿Í º¸µå ¼¿ À§Ä¡¸¦ »ç¿ëÇÏ¿© ±× ¼ø¿­¿¡ ´ëÇÑ findOccupiedBoardCells() ¸Þ¼ÒµåÀÇ °á°ú¸¦ °®°íÀÖ´Ù. Listing 10Àº ±×¿Í°°Àº Å×À̺íÀ» º¸À¯ÇÏ°í ÀÖ´Â Piece Ŭ·¡½ºÀÇ ¾÷µ¥ÀÌÆ® ¹öÀüÀÌ´Ù:

Listing 10. findOccupiedBoardCells() ¸Þ¼ÒµåÀÇ °á°ú ij½ÌÇϱâ

public class Piece {
  private Piece[] permutations = new Piece[NUMBEROFPERMUTATIONS];
  private ArrayList[][] occupiedBoardCells =
    new ArrayList[Piece.NUMBEROFCELLS][Board.NUMBEROFCELLS];

  private void generatePermutations(Board board) {
    Piece prevPermutation=this;
    for (int i = 0; i < NUMBEROFPERMUTATIONS; i++) {
      // The original nextPermutation() has been renamed
      permutations[i]=
        ((Piece)prevPermutation.clone()).nextPermutation_orig();
      prevPermutation=permutations[i];
    }

    // Calculate occupied board cells for every permutation
    for (int i = 0; i < NUMBEROFPERMUTATIONS; i++) {
      permutations[i].generateOccupiedBoardCells(board);
    }
  }

  private void generateOccupiedBoardCells(Board board) {
    for (int i = 0; i < Piece.NUMBEROFCELLS; i++) {
      for (int j = 0; j < Board.NUMBEROFCELLS; j++) {
        occupiedBoardCells[i][j]=new ArrayList();
        resetProcessed(); // We're going to process the piece
        board.findOccupiedBoardCells(occupiedBoardCells[i][j],
                                     pieceCells[i],
                                     board.getBoardCell(j));
      }
    }
  }

  public Piece nextPermutation() {
    if (currentPermutation == NUMBEROFPERMUTATIONS)
      currentPermutation = 0;

    // The new implementation of nextPermutation() 
    // accesses the cache
    return permutations[currentPermutation++];
  }

  public ArrayList 
    getOccupiedBoardCells(int pieceCellIdx, int boardCellIdx) {
    // Access requested data in cache
    return occupiedBoardCells[pieceCellIdx][boardCellIdx];
  }
}

generatePermutations() ¸Þ¼Òµå´Â Piece °´Ã¼°¡ ¸¸µé¾îÁú¶§ ÀÛµ¿ÇÑ´Ù. ÀÌ°ÍÀº Á¶°¢ÀÇ ¸ðµç ¼ø¿­À» °è»êÇÏ°í ±×·¯ÇÑ ¼ø¿­¿¡ ´ëÇÑ findOccupiedBoardCells() ¸Þ¼ÒµåÀÇ ¸ðµç °¡´ÉÇÑ °á°ú¸¦ ij½ÌÇÑ´Ù. ä¿öÁø º¸µå ¼¿À» °è»êÇϱ⠿øÇϸé ÆÛÁñº¸µå·Î ¾×¼¼½º ÇؾßÇÑ´Ù´Â °ÍÀÌ ¸íÈ®ÇØ Á³´Ù. ¶ÇÇÑ ÇÑ Á¶°¢ÀÇ ¼ø¿­Àº ¿ø·¡ Piece °´Ã¼ÀÇ Å¬·ÐÀ̶ó´Â Á¡À» ÁÖ¸ñÇ϶ó. Piece¸¦ º¹Á¦´Â ÀÌ°ÍÀÇ ¼¿ ¸ðµÎ¸¦ º¹»çÇÏ´Â °úÁ¤ÀÌ Æ÷ÇԵȴÙ.

ÀÌÁ¦ ¸¶Áö¸·À¸·Î ÇؾßÇÒ ÀÏÀº Board Ŭ·¡½ºÀÇ placePiece() ¸Þ¼Òµå¿¡¼­ ij½Ã¸¦ ¾×¼¼½ºÇÏ´Â °ÍÀÌ´Ù. (Listing 11):

Listing 11. ä¿öÁø º¸µå ¼¿ ij½Ã¿¡ ¾×¼¼½ºÇϱâ

public class Board {
  public boolean 
    placePiece(Piece piece, int pieceCellIdx, int boardCellIdx) {
    // Get all the boardCells that this piece would occupy
    ArrayList occupiedBoardCells =
      piece.getOccupiedBoardCells(pieceCellIdx, boardCellIdx);
    ...
  }
}

ÇÁ·Î±×·¥ Çѹø ´õ ½ÇÇàÇϱâ
ÆÛÁñ Ç®ÀÌ ÇÁ·Î±×·¥ÀÇ ¾÷µ¥ÀÌÆ® ¹öÀüÀÇ ¼Ò½ºÄÚµå´Â meteor.caching ij½Ì ÆÐÅ°Áö¿¡ ÀÖ´Ù. java meteor.caching.Solver¸¦ ½ÇÇàÇÏ¸é ³î¶ó¿î ÆÛÆ÷¸Õ½º Çâ»óÀ» º¸°ÔµÈ´Ù. Å×½ºÆ® ¸Ó½Å¿¡¼­µµ ¸ðµç ¼Ö·ç¼ÇÀÌ 25ÃÊ ¾È¿¡ °¡´ÉÇß´Ù. ij½Ìµµ 6¹è³ª ºü¸¥ ¼Óµµ·Î °á°ú°¡ ³ª¿Ô´Ù. -verbose:gc ½ºÀ§Ä¡¸¦ »ç¿ëÇÑ´Ù¸é °¡ºñÁö Ä÷º¼ÇÀÌ ´õÀÌ»ó ¹®Á¦°¡ ¾Æ´Ï¶ó´Â °ÍÀ» ¾Ë°ÔµÈ´Ù.

ij½Ã¸¦ ±¸ÇöÇϱâ À§ÇØ µµÀÔÇÑ Ãß°¡ ÄÚµå´Â ÇÁ·Î±×·¥À» º¹ÀâÇÏ°Ô ÇÑ´Ù. ÀÌ°ÍÀº Áß°£ °á°ú¸¦ ÀúÀåÇÏ¿© °è»ê ½Ã°£À» ÁÙÀÌ·Á ÇÒ ¶§ ¹ß»ýÇÏ´Â ÀüÇüÀûÀÎ ´ÜÁ¡ÀÌ´Ù. ÇÏÁö¸¸ ÀÌ °æ¿ì ÆÛÆ÷¸Õ½º¿¡¼­ ¾òÀº À̵æÀº º¹À⼺À» ´É°¡ÇÑ´Ù.

ÇÁ·Î±×·¡¹Ö ÃÖÀûÈ­
ÆÛÁñ Ç®ÀÌ ÇÁ·Î±×·¥À» À§ÇÑ ÃÖÀûÈ­ ÇÁ·Î¼¼½º¿¡¼­ ¶Ç ÇϳªÀÇ °¡´ÉÇÑ ¹æ¹ýÀº Àú¼öÁØ ÀÚ¹Ù ÄÚµå ÃÖÀûÈ­ À̵ð¾öÀ» »ç¿ëÇÏ´Â °ÍÀÌ´Ù. ¿ì¸®´Â ¾ÖÇø®ÄÉÀ̼ǿ¡¼­ ¾î¶² ½ºÆ®¸µµµ Á¶ÀÛÇÏÁö ¾Ê¾Ò´Ù. µû¶ó¼­ Àß ¾Ë·ÁÁø StringBuffer À̵ð¾öÀ» Àû¿ëÇÏ´Â °ÍÀº ¾µ¸ð°¡ ¾ø´Ù. Á÷Á¢ÀûÀÎ ¸â¹ö ¾×¼¼½º·Î °ÔÅÍ(getter)¿Í ¼¼ÅÍ(setter)¸¦ ¹Ù²ÞÀ¸·Î¼­ °ÔÅÍ¿Í ¼¼ÅÍ¿¡ ´ëÇÑ ¸Þ¼Òµå È£Ãâ ¿À¹öÇìµå¸¦ ÇÇÇÒ ¼ö ÀÖ´Ù. ÇÏÁö¸¸ ÀÌ°ÍÀº ÄÚµå ÁúÀ» °­µî½ÃÅ°°í Å×½ºÆ® °á°ú ÀÌ´Â ¼ÓµµÇâ»óÀ» ÀüÇô °¡Á®¿ÀÁö ¾ÊÀ½À» ¾Ë ¼ö ÀÖ´Ù. final ¸Þ¼ÒµåÀÇ »ç¿ëµµ ¸¶Âù°¡ÁöÀÌ´Ù. ¸Þ¼Òµå¸¦ final·Î ¼±¾ðÇÔÀ¸·Î¼­ µ¿Àû ¹ÙÀεùÀ» ÇÇÇÏ°í ÀÚ¹Ù °¡»ó ¸Ó½ÅÀÌ Á»´õ È¿À²ÀûÀÎ Á¤Àû ¹ÙÀεùÀ» »ç¿ëÇÒ ¼ö ÀÖµµ·Ï ÇÒ ¼ö ÀÖ´Ù. ¶ÇÇÑ ÀÚ¹Ù ÄÄÆÄÀÏ·¯ÀÇ -0 ÃÖÀûÈ­ ½ºÀ§Ä¡ÀÇ »ç¿ëÀº ½ÇÁ¦ÀûÀÎ ÆÛÆ÷¸Õ½º Áõ°¡¸¦ °¡Á®¿ÀÁö ¾Ê´Â´Ù.

¹Ì¹ÌÇÑ ½ÇÇà ¼ÓµµÇâ»óÀº prune() ¸Þ¼Òµå ±¸ÇöÀ» ¹ßÀü½ÃÄѼ­ ¾ò¾î³¾ ¼ö ÀÖ´Ù. Listing 7 ÀÇ ÄÚµå´Â Ç×»ó Àç±ÍÀûÀÎ getIslandSize() ¸Þ¼Òµå·Î È£ÃâÇÑ´Ù. º¸µå ¼¿ÀÌ ÀÌ¹Ì ÇÁ·Î¼¼½º µÇ¾îÀְųª ºñ¾îÀÖÁö ¾ÊÀ» ¶§¿¡µµ ±×·¸´Ù. getIslandSize()¸¦ È£ÃâÇϱâ Àü¿¡ Àû±ØÀûÀ¸·Î ÀÌ°ÍÀ» Á¡°ËÇÑ´Ù¸é 10%ÀÇ Çâ»óÀ» ±â´ëÇÒ ¼ö ÀÖ´Ù.

Àú¼öÁØ ÃÖÀûÈ­ÀÇ °á°ú´Â ¾ÆÁÖ ÀÛÀº ÆÛÆ÷¸Õ½º Áõ°¡¸¦ °¡Á®¿Â´Ù. ÀÌ·¯ÇÑ ÃÖÀûÈ­ ±â¼úÀº ÄÚµåÀÇ ÁúÀ» °­µî½ÃŲ´Ù´Â ´ÜÁ¡µµ °¡Áö°í ÀÖ°í µû¶ó¼­ Àú¼öÁØÀÇ ÃÖÀûÈ­ »ç¿ëÀº ¸Å·ÂÀûÀÌÁö ¾Ê´Ù.

°á·Ð
ÆÛÁñ Ç®ÀÌ ÇÁ·Î±×·¥ÀÇ ±¸ÇöÀ» Çâ»ó½ÃÅ°±â À§ÇÑ ¸ðµç ³ë·ÂÀº È®½ÇÈ÷ È¿°ú°¡ ÀÖ¾ú´Ù. Table 1¿¡´Â ¿ì¸®°¡ ¸¸µç °¢°¢ÀÇ ¹öÀü°ú ½ÇÇà½Ã°£À» ¿ä¾àÇØ ³õ¾Ò´Ù. Àüü °á°ú´Â 2,000,000 ¹èÀÇ ¼Óµµ Çâ»óÀÌ´Ù.

Table 1. ½ÇÇà ½Ã°£ ºñ±³
Version ½Ã°£ (ÃÊ)
meteor.initial ~ 60,422,400 (¾à 2³â)
meteor.algorithm 157
meteor.caching 25

ÇÏÁö¸¸ ÀÌ ÃÖÀûÈ­°¡ ¾Æ¹«¸® ³î¶ó¿öµµ ÀÌ ½ÇÇè¿¡¼­ ¿ì¸®°¡ ¹è¿ï ¼ö ÀÖ´Â °ÍÀÌ ¹«¾ùÀΰ¡ ¶ó´Â Áß¿äÇÑ Áú¹®ÀÌ ³²¾ÆÀÖ´Ù. ¿ì¸®°¡ »ç¿ëÇß´ø ´Ù¾çÇÑ ÃÖÀûÈ­ ±â¼úÀº °¢°¢ ÀåÁ¡°ú ´ÜÁ¡À» °®°íÀÖ´Ù. ±×µéÀ» Á¶ÇÕÇÏ¿© ÇϳªÀÇ ÃÖÀûÈ­ ÇÁ·Î¼¼½º·Î ¸¸µå´Â °ÍÀº »ç¿ë¹ýÀ» ¸íÈ®È÷ ÇÏ°í ¾ÖÇø®ÄÉÀ̼ÇÀÇ ±¸½ÄÈ­¸¦ ¹æÁöÇÑ´Ù.

  • ¾Ë°í¸®Áò Çâ»ó°ú °°Àº °í¼öÁØ ÃÖÀûÈ­ ±â¼úÀº »ó´çÇÑ ÀáÀç·ÂÀÌ ÀÖ´Ù. ÆÛÆ÷¸Õ½º°¡ Áß¿äÇÑ(performance-critical) ÄÚµå Á¶°¢À» ÃÖÀûÈ­ ½ÃÄÑ¾ß ÇÑ´Ù¸é ¿ì¼± ÀÌ Äڵ尡 ±¸ÇöÇÏ´Â ÇÁ·Î¼¼½º¸¦ ºÐ¼®ÇÑ´Ù. ÇÁ·Î¼¼½º¸¦ ½Ã°¢È­ÇÏ´Â °ÍÀº ÇÁ·Î¼¼½º ÀÌÇظ¦ À§ÇÑ ÃÖ¼±ÀÇ ¹æ¹ýÀÌ´Ù. ¶ÇÇÑ ´Ù¸¥ °¢µµ·Î ¹®Á¦¸¦ ¤¾î°¡¶ó. ¿ø·¡ °í¾ÈÇÑ°Í º¸´Ù ÈξÀ ³ªÀº ¼Ö·ç¼ÇÀ» µµÃâÇØ ³¾ °ÍÀÌ´Ù. ÀÌ·± Á¾·ùÀÇ ÃÖÀûÈ­´Â ÀϹÝÈ­°¡ ¾î·Æ´Ù. ¸ðµç ¾Ë°í¸®ÁòÀº ƯÁ¤ ¾ÖÇø®ÄÉÀÌ¼Ç µµ¸ÞÀο¡ µû¶ó ´Ù¸£°í ÀϹÝÀûÀÎ °¡À̵å¶óÀεµ ºÎÁ·ÇÏ´Ù. ÇÁ·Î±×·¡¸Ó°¡ ¾ó¸¶³ª âÁ¶ÀûÀÌ µÇ´Â°¡¿¡ ´Þ·ÁÀÖ´Ù.

  • ÀÏ´Ü ÁÁÀº ½ÇÇà ¼Ö·ç¼ÇÀÌ ÀÖ´Ù°í È®½ÅÇÑ´Ù¸é ÀÌ°ÍÀ» ±â¼úÀû ÆÛÆ÷¸Õ½º Çâ»ó ±â¼ú¿¡ Àû¿ëÇÒ ¶§ÀÌ´Ù. ±âº»ÀûÀÎ °³³äÀº ½Ã°£ º¹Àâµµ(time complexity)¿Í µ¥ÀÌÅÍ º¹Àâµµ(data complexity)¸¦ ±³È¯ÇÏ´Â °ÍÀÌ´Ù. °´Ã¼ ij½Ã´Â ±×¿Í°°Àº ±â¼úÀÇ ÀüÇüÀûÀÎ ¿¹ÀÌ´Ù. ÀÚ¹Ù ÇÁ·Î±×·¥¿¡¼­ °´Ã¼ ij½Ã´Â °ªºñ½Ñ °´Ã¼ »ý¼ºÀ̳ª °¡ºñÁö Ä÷º¼Ç ¿À¹öÇìµå¸¦ ÇÇÇÏ°íÀÚ ÇÒ ¶§ ƯÈ÷ À¯¿ëÇÏ´Ù. ÀÌ·¯ÇÑ Á¾·ùÀÇ ½Ã½ºÅÛÀº ÇÁ·Î±×·¥¿¡ Ãß°¡ÀûÀÎ ±â¹Ý Äڵ带 Ãß°¡ÇؾßÇϱ⠶§¹®¿¡ µµÀÔÀ» ³Ê¹« ¼­µÎ¸£Áö ¸»¾Æ¾ß ÇÑ´Ù. Äڵ尡 º¹ÀâÇØ Áú ¼ö·Ï ÃÖÀûÈ­´Â ´õ¿í ¾î·Á¿öÁø´Ù.

  • ¸¶Áö¸·À¸·Î Àú¼öÁØ ÇÁ·Î±×·¡¹Ö ÃÖÀûÈ­¸¦ Àû¿ëÇÒ ¼ö ÀÖ´Ù. ´ëºÎºÐÀÇ ÀÚ¹Ù ÇÁ·Î±×·¡¸ÓµéÀº ÀÌ·¯ÇÑ Á¾·ùÀÇ ±â¼ú¿¡ Àͼ÷ÇÏ´Ù. ÇÏÁö¸¸ ½ÇÁ¦ ÇÁ·Î±×·¥¿¡¼­ ¾ò´Â ÀÌÀÍÀº Á¦ÇѵǾî ÀÖ´Ù. °¡´ÉÇÑ °÷¿¡ Àû¿ë½ÃÅ°µÇ ÀÌ·¯ÇÑ Á¾·ùÀÇ À̵ð¾ö¿¡ ÃÖÀûÈ­ÀÇ Æ÷Ä¿½º¸¦ ¸ÂÃßÁö ¸»¶ó. Àß ¾Ë·ÁÁø ÆÛÆ÷¸Õ½º Æ®·¥À» ¹æÁöÇϱâÀ§ÇÑ ÇÁ·Î±×·¡¹Ö Åø¼ÂÀÇ ÀϺηΠ»ç¿ëÇ϶ó.

ÆÛÁñ Ç®ÀÌ ÇÁ·Î±×·¥¿¡¼­ ´Ù¾çÇÑ ÃÖÀûÈ­ ±â¼úÀ» Á¶ÇÕÇؼ­ ¾òÀº ³î¶ó¿î ÆÛÆ÷¸Õ½º Çâ»óÀ¸·Î, ¸ðµç ÀÚ¹Ù ÇÁ·Î±×·¡¸ÓµéÀÌ ±×µéÀÇ Äڵ带 µÇµ¹¾Æ º¸°í ¾î¶»°Ô À̸¦ ÃÖÀûÈ­ÇÏ´ÂÁö¸¦ ¿¬±¸Çϵµ·Ï µ¿±â¸¦ ºÎ¿©ÇÒ ¼ö Àֱ⸦ ¹Ù¶õ´Ù.

Âü°íÀÚ·á

ÇÊÀÚ¼Ò°³
Erwin VervaetÀº ¼ÒÇÁÆ®¿þ¾î ¿£Áö´Ï¾îÀÌ´Ù. 1996³âºÎÅÍ ÀÚ¹Ù ¾ð¾î¸¦ ´Ù·ðÀ¸¸ç º§±â¿¡ÀÇ Katholieke Universiteit Leuven¿¡¼­ ÄÄÇ»ÅÍ °øÇÐ ÇÐÀ§¸¦ ¹Þ¾Ò´Ù. ÇöÀç IT ¿¬±¸, ÀÌÄ¿¸Ó½º ÇÁ·ÎÁ§Æ®, ¿ÀǼҽº À̴ϼÅƼºê, »ê¾÷ ¼ÒÇÁÆ®¿þ¾î ½Ã½ºÅÛ ºÐ¾ß¿¡¼­ ÀÏÇÏ°í ÀÖ´Ù. ÇÁ¸®·£½º ÄÁ¼³ÅÏÆ®À̸ç ÀÚ¹Ù·Î °´Ã¼ ÁöÇâ ºñÁö´Ï½º Á¤º¸ ½Ã½ºÅÛÀ» ±¸ÇöÇÏ°í ÀÖ´Ù.


Maarten De Cock´Â ÀÚ¹Ù ÇÁ·Î±×·¡¸ÓÀÌ´Ù. ƯÈ÷ ±ú²ýÇÏ°í ºü¸¥ ÀÚ¹Ù Äڵ忡 °ü½ÉÀ» °®°í ÀÖ´Ù. º§±â¿¡ÀÇKatholieke Hogeschool LeuvenÀ» Á¹¾÷ÇÑ ÈÄ 99³â ºÎÅÍ ÀÚ¹Ù ¾ð¾î¸¦ ´Ù·ç±â ½ÃÀÛÇß´Ù.ÇöÀç ASQdotCOMÀÇ ÄÁ¼³ÅÏÆ®·Î ÀÏÇÏ°í ÀÖ´Ù.



ÀÌ ±â»ç¿¡ ´ëÇÏ¿© ¾î¶»°Ô »ý°¢ÇϽʴϱî?

Á¤¸» ÁÁ´Ù (5) ÁÁ´Ù (4) ±×Àú±×·¸´Ù (3) ¼öÁ¤º¸¿ÏÀÌ ÇÊ¿äÇÏ´Ù(2) ÇüÆí¾ø´Ù (1)

  È¸»ç¼Ò°³  |  °³ÀÎÁ¤º¸ º¸È£Á¤Ã¥  |  ¹ý·ü  |  ¹®ÀÇ