1211. [S/W 문제해결 기본] 2일차 - Ladder2

1. 딱히 알고리즘이 생각 나지 않아 모든 사다리를 다 이동하도록 구현하였다.

 

2. 좌, 우 이동이 가능한 경우 해당 칸의 끝까지 이동 후 다리 아래로 내려가도록 구현하였다.

 

todo : 더 좋은 방법의 알고리즘을 적용시키기.

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14BgD6AEECFAYh

SW Expert Academy

 

소스코드

#include <stdio.h>
#define MAX_NODE 100
using namespace std;
const int MAX_RESULT = 0x7fffffff;
int map[MAX_NODE][MAX_NODE];
int dx[] = { -1, 1 };
int result = MAX_RESULT;
int answer = 0;
int ladder(int x, int y)
{
	int count = 2;
	int cx = x;
	int cy = y+1;
	while (cy < MAX_NODE) {
		for (int i = 0; i < 2; i++) {
			int nx = cx + dx[i];
			if (nx < 0 || nx >= MAX_NODE) continue;
			if (map[cy][nx] == 1) {
				count++;
				while (1) {
					if (map[cy][nx] == 0) {
						nx += (i == 0) ? 1 : -1;
						count--;
						break;
					}
					if ((i == 0 && nx == 0) || (i == 1 && nx == MAX_NODE -1)) {
						break;
					}
					nx += dx[i];
					count++;
				}
				cx = nx;
				break;
			}
		}
		cy++;
		count++;
		if (count > result) {
			return MAX_RESULT;
		}
	}
	return count;
}
void solution()
{
	for (int i = 0; i < MAX_NODE; i++) {
		if (map[0][i]) {
			int n = ladder(i, 0);
			if (result >= n) {
				answer = i;
				result = n;
			}
		}
	}
}

int main()
{
	for (int k = 0; k < 10; k++) {
		int n;
		scanf("%d", &n);
		for (int i = 0; i < MAX_NODE; i++) {
			for (int j = 0; j < MAX_NODE; j++) {
				scanf("%d", &map[i][j]);
			}
		}
		result = MAX_RESULT;
		answer = 0;
		solution();
		printf("#%d %d\n", n, answer);
	}
}