[D4] SWEA [S/W 문제해결 기본] 2일차 - Ladder1 C++ 구현, 시뮬레이션, 브루트포스 알고리즘

 

리뷰

 

SW Expert Academy

진짜 맞왜틀을 엄청 외쳤는데 진짜 맞왜틀이였다, SWEA의 기본 문제들 처럼 테스트케이스의 개수가 주어지는 것이 아닌, 테스트 케이스는 10개 고정이고 각 문제의 번호가 맵 입력 전에 주어지는 구조였다.

첫 번째 케이스만 맞고 나머지가 오답 처리가 된다면 꼭 Input파일을 다운받아 한번 확인해 보길 바란다.

 

 

전역 변수

• t : 각 문제의 번호를 입력 받을 변수
• lst : 맵 정보를 입력 받아 저장할 정수형 2차 배열
• v : 가로 선을 만나 꺾인 경우의 방문 처리를 위한 정수형 3차 배열
• dy : 좌우로 이동하기 위한 방향 배열

 

함수

1. input

void input()

 

맵 정보를 입력받기 위한 함수

 

2. chk

bool chk(int sy, int dir)

 

사다리를 타고 내려가는 시뮬레이션을 하기 위한 함수

1. 매개변수로 시작 col인덱스 sy와 초기 방향 정보 dir를 입력받는다.
2. 사다리의 높이 sx를 0으로 초기화 하고 사다리의 맨 위에서부터 내려가기 시작한다.
3. sx가 100 미만일 경우 반복되는 while루프를 실행한다.
4. 만약 dir이 0이 아니라면 현재 dir방향으로 이동할 위치를 ny로 초기화 해준다.
5. ny가 범위 내이면서 맵 상에서 0이 아니라면 이동을 진행해도 된다.
6. 다만 이미 방문처리가 되어 있는 사다리라면 break처리하여 바로 탐색을 멈추어준다.
7. 방문처리 되어있지 않다면 방문처리 후 sy를 ny로 최신화 하고 continue 처리하여 탐색을 이어간다.
8. 만약 ny가 범위 밖이거나 더 이상 옆으로 이동할 사다리가 없다면 dir를 0으로 바꿔주고 아래로 내려가준다.
9. 만약 방향이 dir인 경우 왼쪽 오른쪽으로 이동할 사다리가 있는지 부터 체크해 준다.
10. 좌우 중 한 군데로 이동 가능하면서 방문되어 있지 않다면 이동 후 dir를 왼쪽이면1, 오른쪽이면2로 만들어 준다.
11. 만약 이동이 불가능 하다면 sx를 증가시키며 아래로 내려가 주면 된다.
12. while문이 종료되었을때 sx가 100 즉 맨 아래까지 내려왔고, lst[99][sy]가 2라면 true를 리턴한다.
13. 위 케이스가 아닐 경우 모두 false를 리턴해 준다.

3. solution

int solution()

 

출발 가능한 사다리가 있다면 모두 돌려보기 위한 함수

1. 사다리의 맨 위가 1인 칼럼이 있다면 chk함수를 호출해 준다.
2. 만약 chk함수의 리턴이 true라면 곧 바로 해당 칼럼의 인덱스를 리턴해 준다.

 

문제풀이

1. 10번의 반복문을 실행해 준다.
2. 변수 t에 문제의 번호를 입력 받아준다.
3. memset 메서드를 통해 이전 케이스에서 사용한 방문 배열을 초기화 해준다.
4. input함수를 통해 맵 정보를 입력 받아준다.
5. 각 테스트 케이스마다 문제 번호를 넣고 solution함수의 리턴값을 출력해 준 뒤 줄바꿈을 해준다.

 

참고 사항

테스트케이스는 무조건 10번으로 고정되어 있다.

각 테스트 케이스 마다 맵을 입력 받기 전에 문제 번호를 입력해 주어야 한다.

 

 

정답 코드

#include<iostream>
#include<cstring>
using namespace std;

int t, ans;
int lst[100][100];
int v[100][100][3];
int dy[] = { 0, -1, 1 };

void input() {
	for (int i = 0; i < 100; ++i) {
		for (int j = 0; j < 100; ++j) {
			cin >> lst[i][j];
		}
	}
}

bool chk(int sy, int dir) {
	int sx = 0;
	while (sx < 100) {
		if (dir) {
			int ny = sy + dy[dir];
			if (0 <= ny && ny < 100 && lst[sx][ny]) {
				if (v[sx][ny][dir]) break;
				v[sx][ny][dir] = 1;
				sy = ny;
				continue;
			}
			dir = 0;
			sx++;
			continue;
		}

		int l = sy + dy[1], r = sy + dy[2];
		if (0 <= l && lst[sx][l]) {
			dir = 1;
			if (v[sx][l][dir]) break;
			v[sx][l][dir] = 1;
			sy = l;
		}
		else if (r < 100 && lst[sx][r]) {
			dir = 2;
			if (v[sx][r][dir]) break;
			v[sx][r][dir] = 1;
			sy = r;
		}
		else sx++;
	}
	if (sx == 100 && lst[99][sy] == 2) return true;
	return false;
}

int solution() {
	for (int i = 0; i < 100; ++i) {
		if (lst[0][i] && chk(i, 0)) return i;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	for (int c = 1; c <= 10; ++c) {
		cin >> t;
		memset(v, 0, sizeof(v));
		input();
		cout << "#" << t << " " << solution() << "\n";
	}
}