글 읽기 - 시간초과..

oyj0594 7년 전 0

테스트 케이스 다 통관데 시간초과 나네요..

dfs 를 리컬젼으로 했는데 따로 스택을 둔다고 시간 줄어들까요??

dfs_search에서 조건 8가지 ( 위로, 아래로, 왼쪽, 오른쪽 각각 벽 있다면 부수고 가기 or 벽 없다면 그냥 가기)

로 나누어서 리컬시브하게 짰습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX 10000

void dfs_search(char**maze, int y, int x, int row, int column, int bomb, int wall);
int min_bomb = MAX;

int main(){

	int row = 0;
	int column = 0;
	char **maze = NULL;

	scanf("%d %d", &column, &row);

	maze = (char **)malloc(sizeof(char *) * row);
	for (int i = 0; i < row; i++)
		maze[i] = (char *)malloc(sizeof(char) * column + 1);

	for (int i = 0; i < row; i++)
		scanf("%s", maze[i]);


	dfs_search(maze, 0, 0, row, column, 0, 0);

	printf("%d\n", min_bomb);



	for (int i = 0; i < row; i++)
		free(maze[i]);
	free(maze);

	return 0;
}


void dfs_search(char**maze, int y, int x, int row, int column,int bomb, int wall){


	if (y == row - 1 && x == column - 1){

		if (min_bomb > bomb)
			min_bomb = bomb;

		return;
	}

	if (min_bomb < bomb)
		return;

	maze[y][x] = '3'; // 지나감

	//조건 8가지 

	//위로 2가지 ( 벽 뚫기 and 뚫려있으면 가기)
	if (y > 0 && maze[y - 1][x] == '0')
		dfs_search(maze, y - 1, x, row, column, bomb, 0);
		
	if (y > 0 && maze[y - 1][x]=='1')
		dfs_search(maze, y - 1, x, row, column, bomb + 1, 1);

	//밑으로 2가지
	if (y < row - 1 && maze[y + 1][x] == '0')
		dfs_search(maze, y + 1, x, row, column, bomb, 0);

	if (y < row - 1 && maze[y + 1][x] == '1')
		dfs_search(maze, y + 1, x, row, column, bomb + 1, 1);

	//오른쪽 2가지
	if (x < column - 1 && maze[y][x + 1] == '0')
		dfs_search(maze, y, x + 1, row, column, bomb, 0);

	if (x < column - 1 && maze[y][x + 1] == '1')
		dfs_search(maze, y, x + 1, row, column, bomb + 1, 1);

	//왼쪽 2가지
	if (x > 0 && maze[y][x - 1] == '0')
		dfs_search(maze, y, x - 1, row, column, bomb, 0);

	if (x > 0 && maze[y][x - 1] == '1')
		dfs_search(maze, y, x - 1, row, column, bomb + 1, 1);


	// 지나간 칸 되돌리기
	if (wall == 1)
		maze[y][x] = '1';
	else
		maze[y][x] = '0';

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과..

oyj0594 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말