JHB의 프로그래밍 삽질기

길 찾기 알고리즘에서 방향 꺾는 부분을 if 문줄여서 간결하게 표현하기 본문

PROGRAMMING/Algorithm

길 찾기 알고리즘에서 방향 꺾는 부분을 if 문줄여서 간결하게 표현하기

roter 2011.03.23 16:17
int go( int search, int a, int b, int state, int turning ) { if( found == 1 ) return 1; if( turning > 3 ) //맨처음 시작을 생각해서 3임 { return 0; } if( map[a][b] == search && state != START ) { sx = a; sy = b; found = 1; return 1; } v[a][b] = 1; //U if( v[a-1][b] == 0 && ( map[a-1][b] == 0xFF || map[a-1][b] == search ) && a > 0 ) { if( state == U ) go( search, a-1, b, U, turning ); else go( search, a-1, b, U, turning + 1 ); } //L if( v[a][b-1] == 0 && ( map[a][b-1] == 0xFF || map[a][b-1] == search ) && b > 0 ) { if( state == L ) go( search, a, b-1, L, turning ); else go( search, a, b-1, L, turning + 1 ); } //R if( v[a][b+1] == 0 && ( map[a][b+1] == 0xFF || map[a][b+1] == search ) && b < COL-1 ) { if( state == R ) go( search, a, b+1, R, turning ); else go( search, a, b+1, R, turning + 1 ); } v[a][b] = 0; return 0; }


사천성 같이 두번 이내로 꺾이는 프로그램의 길을 찾을려고 이런 식으로 구현했는데..
if문이 너무 많아서 보기가 좋지 않다. 실제로 길찾기 프로그램을 짜다보면 위, 양옆, 아래 이렇게 4부분을 분기처리 해야하는 상황이 생긴다.
근데 그러면 소스가 너무 길어져서 싫다 -.-;; 그리고 개인적으로 if문이 많은것도 좋아하지 않는다.

그럼 if문을 어떻게 없앨 수 있을까?
다음과 같이 짤 수 있다!!

int sx,sy;
int found;

const int START = -1;
const int U = 0;
const int L = 1;
const int R = 2;
const int D = 3;


int go( int search, int a, int b, int state, int turning )
{

	// U L R D
	int dx[] = { -1, 0, 0, 1 };
	int dy[] = { 0, -1, 1, 0 };

	if( found == 1 )
		return 1;

	if( turning > 3 ) //맨처음 시작을 생각해서 3임
	{
		return 0;
	}

	if( map[a][b] == search && state != START )
	{
		sx = a;
		sy = b;
		found = 1;
		return 1;
	}

	v[a][b] = 1;



	for( int i = 0; i < 4; i++ )
	{
		int x = a+dx[i];
		int y = b+dy[i];
		if( x >= 0 && x < ROW && y > 0 && y < COL &&
			v[x][y] == 0 && ( map[x][y] == 0xFF || map[x][y] == search ) )
		{
			if( state == i )
				go( search, x, y, i, turning );
			else
				go( search, x, y, i, turning+1 );
		}
	}
	v[a][b] = 0;
	return 0;
}


dx와 dy라는 변수의 추가와 함께 if문이 4개나 사라지면서 코드가 짧아졌다!!
0,1,2,3이 각각 U,L,R,D 이다. 포문은 그걸 뱅글뱅글 도는 것이다.

재밌는것 하나 더... 심지어 세줄이나 더 줄일 수 있다.

이렇게!

for( int i = 0; i < 4; i++ )
	{
		int x = a+dx[i];
		int y = b+dy[i];
		if( x >= 0 && x < ROW && y > 0 && y < COL &&
			v[x][y] == 0 && ( map[x][y] == 0xFF || map[x][y] == search ) )
		{
			go( search, x, y, i, turning + (state != i));
		}
	}

정말 엄청난 센스 아닌가????
( state != i ) 을 더하다니..

물론 가독성은 제일 위에 코드가 나은 것 같지만.. 짧은 코드 선호자라면 저런 방법으로 할 수 있다는 사실 ㅎㅎ

커링님 오늘도 감사
10 Comments
  • 프로필사진 천현석 2012.07.02 10:04 신고 안녕하세요 알고리즘 잘봤습니다 ^^ 알고리즘 이용해서 꺽여서 짝맞추는 부분까지는 실행 했는데요. 짝이맞았을때에 라인을 그어주는 부분에서 막히고 있는데요. 라인을 어떤식으로 그리셨는지 알고싶습니다. 이 알고리즘은 갈수있는 방향을 전부다 찾아서 가는거 같은데 정확히 라인을 그을수 있는 포인트를 잡지롤 못했네요 ㅜㅜ 알려주시면 감사하겠습니다.
  • 프로필사진 BlogIcon roter 2012.07.17 20:19 신고 안녕하세요 방문해주셔서 감사합니다 :)
    라인을 긋는다는게 어떤걸 의미하는지 잘 모르겠습니다.
    클릭해서 두 블럭을 사라지게 하는걸 말씀하시는건지요???
    그렇다면 mouse_event를 사용하시면 됩니다.
  • 프로필사진 천현석 2012.08.27 16:13 신고 안녕하세요 ㅎㅎ 좀 늦게 봤네요
    제가 말씀드리는 것은 블럭과 블럭이 맞으면 그사이를 라인 그어주게 되어있잖아요 ㅁ-------ㅁ 요런식으로요 ㅎㅎ
    이부분이 좀 어려워서 물어본거였네요
    이부분도 해결하셨다면 어떻게 하는지좀 알고싶네요
  • 프로필사진 BlogIcon roter 2012.09.01 18:25 신고 안녕하세요~ 매크로 인터페이스를 제작하실려면 mouse_event를 사용하시면 됩니다~~ 제가 질문을 제대로 파악했는지 잘 모르겠네요 ^^;;
  • 프로필사진 불아 2015.06.09 21:25 신고 감사합니다. 도움이 많이 되었습니다.
  • 프로필사진 BlogIcon roter 2015.08.30 22:25 신고 들려주셔서 감사합니다^^
  • 프로필사진 sku 2015.10.22 22:45 신고 1. v배열은 무슨값으로 초기화 되어 있는 배열인가요?

    2. 패 두개를 선택하고 go 함수를 처음 호출할 때 turning 파라미터는 0으로 넣고 호출하나요?

    3. 위 코드에서 0xFF는 뭘 의미 하는건가요?

    학부 저학년 수준이라 질문이 저질스럽네여ㅎㅎ 답변좀 부탁드릴께요~

  • 프로필사진 BlogIcon roter 2015.10.22 22:55 신고 안녕하세요~ 방문해주셔서 감사합니다^^
    저도 오랜만에 이 글을 읽었는데 윗부분 코드가 다 날라가있네요.. 시간을 내서 고쳐야 겠습니다. 답변 드리겠습니다.

    1. v배열은 visit 배열입니다. a행 b열에 방문 하였을 경우 v[a][b] = 1이 됩니다. 방문하지 않았을 경우는 당연히 0이겠지요. 따라서 처음에는 모두 0으로 초기화 돼있습니다.

    2. 예 0을 넣고 호출합니다.

    3. map[x][y]의 경우 x행 y열에 있는 패의 값을 갖습니다. 예를 들어 딸기패를 1, 바나나패를 2 .. 이런식으로 설정하고, 3행 5열에 바나나패가 있을 경우 map[3][5] = 2; 이렇게 들어가 있는 것 입니다.
    0xFF는 '비어 있는 길'을 의미합니다.
    소스코드를 보시면 아시겠지만
    v[x][y] == 0 && //x,y로 아직 가지 않았고
    map[x][y] == 0xFF //비어있는 길 또는
    map[x][y] == search //현재 찾고 있는 패 일 경우
    go 를 계속해서 호출한다,
    입니다.

    도움이 되셨길 바랍니다^^
  • 프로필사진 sku 2015.10.24 16:55 신고 한가지만 더 여쭤볼께요~
    음... sx, sy는 현재의 위치 상태(?)를 표시한것 같은데요
    이 변수는 위의 코드 외에 다른 부분에서 사용하시는건가요??

    지금 학기과제로 사천성을 짜려고 참고중이거든요ㅎㅎ

    코드가 깔끔하고 굉장히 파워풀 해보이네요 ㅋㅋ
  • 프로필사진 BlogIcon roter 2015.10.24 17:14 신고 안녕하세요~ 위 코드에 보시면 found=1 하는 순간에 sx, sy에 값을 넣는게 보이실거에요~ 즉, 입력으로 넣은 패와 같은 모양의 패가 있는 곳의 위치를 의미한답니다~
    다시 짜라고 하면 저런 변수 이름으로 짜지 않을것 같은데 예전에 짜서 너무 대충짠 감이 있네요ㅠㅠ
    잘 만드세요~!
댓글쓰기 폼