반응형
연구소랑 유사한 문제. DFS랑 BFS 섞어서 푸는 문제.
이번년도 하반기 삼성 코테에서도 두 번째 문제가 이런 유형이었는데
코테 보고 오니까 이런 유형이 많이 보이네 ~,~
나는 이런 문제를 계속 함수 두 개 만들어서 함수에서 함수 부르는 구조로 품.
이게 최적의 방법인지 모르겠음
"문제 풀이"
<dfs1 함수>에서 전체 map을 확인하며 'o' 이 있는 곳 찾음. -> [dfs 함수] 호출
[dfs 함수]에서는 시작 위치 'o'에서부터 상하좌우 점프 가능한 곳 이동하고, 이동한 맵에서 다시 <dfs1 함수> 호출 -> 이게 return 받으면 다시 이동한 거 초기화
#include<iostream> using namespace std; char board[5][9]; int move_cnt = 0; int pin_num = 0; int smallest_pin_num = 0; int smallest_move_cnt = INT8_MAX; // 백준에선 INT_MAX 사용 -> 컴파일 에러 // 상하좌우 int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; void dfs1(); void dfs(int _x, int _y) { for (int k = 0; k < 4; k++) { int x = _x + dx[k]; int y = _y + dy[k]; int new_x = x + dx[k]; int new_y = y + dy[k]; if ( (x<0 || x>4) || (y<0 || y>8) || (new_x<0 || new_x>4) || (new_y<0 || new_y>8) ) { // 범위를 벗어나면 continue continue; } if (board[x][y]=='o' && board[new_x][new_y]=='.') { // 핀있으면 뛰어 넘을 수 잇음 board[_x][_y] = board[x][y] = '.'; board[new_x][new_y] = 'o'; pin_num--; move_cnt++; dfs1(); pin_num++; move_cnt--; board[_x][_y] = board[x][y] = 'o'; board[new_x][new_y] = '.'; } } } void dfs1() { for (int i = 0; i < 5; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] == 'o') { dfs(i, j); } } } // 반복문 다 돌고, 재귀도 다 돌고 나왔다는 것은 // 더 이상 이동할 수 있는 핀이 없음 if (smallest_pin_num == pin_num && smallest_move_cnt>move_cnt) { smallest_pin_num = pin_num; smallest_move_cnt = move_cnt; } else if (smallest_pin_num>pin_num) { smallest_pin_num = pin_num; smallest_move_cnt = move_cnt; } } int main() { int tc; cin >> tc; for (int i = 0; i < tc; i++) { // 입력받기 for (int i = 0; i < 5; i++) { for (int j = 0; j < 9; j++) { char temp; cin >> temp; if (temp=='o') { pin_num++; smallest_pin_num++; } board[i][j] = temp; } } // 연산 dfs1(); // 출력 cout << smallest_pin_num << " " << smallest_move_cnt << endl; // 초기화 move_cnt = 0; pin_num = 0; smallest_pin_num = 0; smallest_move_cnt = INT8_MAX; } return 0; }
반응형