U E D R , A S I H C RSS

Eight Queen Problem/kulguy

๋А๋‚Œ์ 

๋ฌธ์ œ์— ๋Œ€ํ•œ ๊ฐœ๋žต์ ์ธ ์ดํ•ด๋งŒ ํ•˜๊ณ ์„œ ๋งˆ์น˜ ๊ทธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์™„์ „ํžˆ ์ดํ•ดํ•œ ๋ƒฅ ๋ฌดํ„ฑ๋Œ€๊ณ  ์ฝ”๋”ฉ์— ๋“ค์–ด๊ฐ”๋‹ค๊ฐ€ ์ •๋‹ต์ด๊ณ  ๋ญ๊ณ  ์™„์ „ํžˆ ์—‰์ผœ๋ฒ„๋ ธ์Šต๋‹ˆ๋‹ค. ๊ฒฐ๊ตญ ์ฒ˜์Œ๋ถ€ํ„ฐ ๋‹ค์‹œ ์ฝ”๋”ฉ ์ด์ „ ๋‹จ๊ณ„๋ถ€ํ„ฐ ์ฐจ๊ทผํžˆ ์ค€๋น„ํ•˜์—ฌ ๊ฒจ์šฐ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. ์ฝ”๋”ฉ ์ด์ „์˜ ์—ฌ๋Ÿฌ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋‹จ๊ณ„๋Š” ํ•จ๋ถ€๋กœ ๊ฑด๋„ˆ๋›ธ ๋‹จ๊ณ„๊ฐ€ ์•„๋‹ˆ๋ž€ ๊ฒƒ์„ ๋‹ค์‹œ ํ•œ๋ฒˆ ๋ผˆ ์† ๊นŠ์ด ๊นจ๋‹ฌ์•˜์œผ๋ฉฐ ์„ฑ๋Šฅ์„ ์œ„ํ•ด ์‹œ๊ณต ๊ตํ™˜ ๋ฒ•์น™์„ ๋‚˜๋ฆ„๋Œ€๋กœ ์ ์šฉํ•ด ๋ณด์•˜๋Š”๋ฐ ๊ทธ ํšจ๊ณผ์˜ ์ƒ๋‹นํ•จ์„ ๊ฒฝํ—˜ํ•˜์˜€์Šต๋‹ˆ๋‹ค.

  • ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ค‘์š”ํ•˜๋‹ค
  • ๋””์ž์ธ๋„ ์ค‘์š”ํ•˜๋‹ค.
  • ์„ฑ๋Šฅ์„ ๋†’์ด๊ณ ์ž ํ•œ๋‹ค๋ฉด ์šฐ์„  ์‹œ๊ณต ๊ตํ™˜ ๋ฒ•์น™์„ ์ด์šฉํ•˜์ž.
    ์‹œ๊ณต ๊ตํ™˜ ๋ฒ•์น™์ด ๋ญ์ฃ ?
    ์„ฑ๋Šฅ์ด๋ž€ ๊ฒƒ์„ ํฌ๊ฒŒ ์ˆ˜ํ–‰ ์‹œ๊ฐ„(ๆ™‚)๊ณผ ์ˆ˜ํ–‰์‹œ ํ•„์š”ํ•œ ๋ฉ”๋ชจ๋ฆฌ(็ฉบ)๋ผ๋Š” 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;
}





Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:12
Processing time 0.0090 sec