๋๋์ ¶
๋ฌธ์ ์ ๋ํ ๊ฐ๋ต์ ์ธ ์ดํด๋ง ํ๊ณ ์ ๋ง์น ๊ทธ ์๊ณ ๋ฆฌ์ฆ์ ์์ ํ ์ดํดํ ๋ฅ ๋ฌดํฑ๋๊ณ ์ฝ๋ฉ์ ๋ค์ด๊ฐ๋ค๊ฐ ์ ๋ต์ด๊ณ ๋ญ๊ณ ์์ ํ ์์ผ๋ฒ๋ ธ์ต๋๋ค. ๊ฒฐ๊ตญ ์ฒ์๋ถํฐ ๋ค์ ์ฝ๋ฉ ์ด์ ๋จ๊ณ๋ถํฐ ์ฐจ๊ทผํ ์ค๋นํ์ฌ ๊ฒจ์ฐ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์์์ต๋๋ค. ์ฝ๋ฉ ์ด์ ์ ์ฌ๋ฌ ํ๋ก๊ทธ๋๋ฐ ๋จ๊ณ๋ ํจ๋ถ๋ก ๊ฑด๋๋ธ ๋จ๊ณ๊ฐ ์๋๋ ๊ฒ์ ๋ค์ ํ๋ฒ ๋ผ ์ ๊น์ด ๊นจ๋ฌ์์ผ๋ฉฐ ์ฑ๋ฅ์ ์ํด ์๊ณต ๊ตํ ๋ฒ์น์ ๋๋ฆ๋๋ก ์ ์ฉํด ๋ณด์๋๋ฐ ๊ทธ ํจ๊ณผ์ ์๋นํจ์ ๊ฒฝํํ์์ต๋๋ค.
- ์๊ณ ๋ฆฌ์ฆ์ด ์ค์ํ๋ค
- ๋์์ธ๋ ์ค์ํ๋ค.
- ์ฑ๋ฅ์ ๋์ด๊ณ ์ ํ๋ค๋ฉด ์ฐ์ ์๊ณต ๊ตํ ๋ฒ์น์ ์ด์ฉํ์.
์๊ณต ๊ตํ ๋ฒ์น์ด ๋ญ์ฃ ?
์ฑ๋ฅ์ด๋ ๊ฒ์ ํฌ๊ฒ ์ํ ์๊ฐ(ๆ)๊ณผ ์ํ์ ํ์ํ ๋ฉ๋ชจ๋ฆฌ(็ฉบ)๋ผ๋ 2๊ฐ์ง ์ธก๋ฉด์์ ๋ณธ๋ค๋ฉด ๋ฉ๋ชจ๋ฆฌ์ชฝ์ ์ฑ๋ฅ์ ํฌ์ํด์ ์ํ ์๊ฐ์ ๋์ด์ฌ๋ฆฌ๋ ๊ฒ์ ๋งํฉ๋๋ค. ์ฆ, ์์ฃผ ์ฐ์ผ ๊ฒ ๊ฐ์ ๊ณ์ฐ ๊ฒฐ๊ณผ๋ ๋งค๋ฒ ๊ณ์ฐํ์ง ์๊ณ ๋ฉ๋ชจ๋ฆฌ์ ๋ด์๋๊ฑฐ๋ ์ธ๋ถ์ ์ ์ฅํ๋ค๊ฐ ๊ฐ์ ธ์ค๋ ์์ด ๋๋ ๊ฑฐ์ฃ . ์ ๊ฐ์ ๊ฒฝ์ฐ ๋ฌธ์ ๋ฅผ ํ๊ธฐ ์ํด ์ฒด์คํ ์์ ํธ ํ๋๊ฐ ๋์ผ ๋๋ง๋ค ๋ค์ ํธ์ด ๋์ผ ์ ์๋ "๊ฐ๋ฅํ ์๋ฆฌ๋ฅผ ๊ณ์ฐ"ํด์ ๊ทธ ๋ค์ ํธ์ ๋ฐฐ์นํ๋ ๋ฐฉ์์ ์ฌ์ฉํ์ต๋๋ค. ์ด ๋ "๊ฐ๋ฅํ ์๋ฆฌ๋ฅผ ๊ณ์ฐ"ํ ๊ฒฐ๊ณผ๋ฅผ ๋ฉ๋ชจ๋ฆฌ์ ๋ด์๋๊ณ ๊ณ์ ์ด์ฉํ์์ฃ . ์ฐธ๊ณ ๋ก ์ด ์ฉ์ด์ ๊ฐ๋ ๋ค์ ๊น์ฐฝ์ค๋์ด ๋ง์์ ๊ธฐ๊ณ ํ์ ํ์ด์ฌ ๊ด๋ จ ๊ธฐ์ฌ์์ ๋น์ค๋ฏ๋ฆฌ ์ธ์ฉํ ๊ฒ ์ ๋๋ค. ์ธ์ฉ์ด๋ ๋ณธ๋ ๊ทธ ๋ด์ฉ์ ์ ํํ ์ ๋ฌํด์ผ ํ๋๋ฐ -_-;;; ๋ง์ ๊ธฐ์ฌ๋ฅผ ์ง์ ์ฐธ๊ณ ํด๋ณด์๊ธฐ ๋ฐ๋๋๋ค
See Also ๋ง์2001๋
4์ About Python ๊ธฐ์ฌ - ํ์ด์ฌ ์ต์ ํ๋ก
์์ค ํ์ผ ¶
QueensProblem.java ¶
~cpp public class QueensProblem { // to run, prompt>java QueensProblem x public static void main(String[] args) { QueensProblem problem = new QueensProblem(Integer.parseInt(args[0])); long start = System.currentTimeMillis(); problem.locate(0); System.out.println("์์์๊ฐ(ms) = " + String.valueOf(System.currentTimeMillis() - start)); System.out.println("๊ฐ๋ฅํ ํด๋ต = " + String.valueOf(problem.getSuccessNum())); } public QueensProblem(int queensNum) { this.queensNum = queensNum; board = new Chessboard(queensNum); } public int getSuccessNum() { return successNum; } public boolean locate(int index) { if (index == queensNum) { ++successNum; // System.out.println("์ฑ๊ณต " + String.valueOf(++successNum)); // System.out.println(board); return true; } Chessboard.PointList points = board.getAvailablePoints(); Point point = null; while ((point = points.nextPoint()) != null) { if(point.getY() == index + 1) return false; Queen queen = new Queen(point); board.locate(queen); if (locate(index + 1)) { // return true; board.rollback(); } else { board.rollback(); } } return false; } private Chessboard board; private int queensNum; private int successNum; }
Chessboard.java ¶
~cpp import java.util.*; public class Chessboard { public Chessboard(int size) { this.size = size; queens = new Stack(); availablePointsStack = new Stack(); List availablePoints = new ArrayList(); for (int y = 0; y < size; ++y) for (int x = 0; x < size; ++x) availablePoints.add(new Point(x, y)); availablePointsStack.push(new PointList(availablePoints)); } public void locate(Queen queen) { List availablePoints = new ArrayList(); List points = ((PointList)availablePointsStack.peek()).getPoints(); Iterator pointsIter = points.iterator(); while (pointsIter.hasNext()) { Point point = (Point)pointsIter.next(); if (!queen.canAttack(point)) availablePoints.add(point); } queens.push(queen); availablePointsStack.push(new PointList(availablePoints)); } public void rollback() { queens.pop(); availablePointsStack.pop(); } public PointList getAvailablePoints() { return (PointList)availablePointsStack.peek(); } public String toString() { StringBuffer buff = new StringBuffer(); Iterator iter = queens.iterator(); while (iter.hasNext()) { Queen queen = (Queen)iter.next(); buff.append(queen.getPoint().toString()); buff.append("\n"); } return buff.toString(); } private int size; private Stack queens; private Stack availablePointsStack; public static class PointList { public PointList(List points) { this.points = points; index = 0; } public Point nextPoint() { Point point = null; if (index < points.size()) { point = (Point)points.get(index); ++index; } return point; } public List getPoints() { return points; } public String toString() { StringBuffer buff = new StringBuffer(); Iterator iter = points.iterator(); while (iter.hasNext()) { Point point = (Point)iter.next(); buff.append(point); buff.append("\n"); } return buff.toString(); } private int index; private List points; } }
Queen.java ¶
~cpp public class Queen { public Queen(Point point) { this.point = point; } public boolean canAttack(Point p) { return point.equalsX(p) || point.equalsY(p) || point.isLocatedCrossly(p); } public Point getPoint() { return point; } private Point point; }
Point.java ¶
~cpp public class Point { public Point(int x, int y) { this.x = x; this.y = y; } public boolean equalsX(Point point) { return point.x == x; } public boolean equalsY(Point point) { return point.y == y; } public boolean isLocatedCrossly(Point point) { int diffX = Math.abs(point.x - x); int diffY = Math.abs(point.y - y); return diffX == diffY; } public int getX() { return x; } public int getY() { return y; } public String toString() { return "(" + String.valueOf(x) + ", " + String.valueOf(y) + ")"; } private int x; private int y; }