글 읽기 - 1987 문제 너무 스트레스받아서 올립니다. 2 코드의 차이가 뭔가요 ??

ty576 4년 전 0

제 코드는 시간초과나고 , 아래 코드는 시간 초과가 안난다고 합니다... 제가 보기엔 같은 코드로 푼거같은데 ...이유가 무엇일까요 ??

위가 제 코드 (시간초과 ) 아래가 되는 코드입니다.

import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
 

//////////////////////시간초과 나는 코드 //////////////
public class 알파벳 {
	static int r;
	static int c;
	static int[] dirX = {0,0,-1,1};
	static int[] dirY = {-1,1,0,0};
	static int max= 0;
	static char[][] map;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		r= scan.nextInt();
		c= scan.nextInt();
		map =new char[r][c];
		for(int i=0; i<r; i++) {
			String s = scan.next();
			for(int j =0; j<c; j++) {
				map[i][j] = s.charAt(j);
			}
		}
		LinkedList<Character> list= new LinkedList<Character>(); 
		dfs(0,0,1,list);
		System.out.println(max);
	}

	private static void dfs(int i, int j,int cnt, LinkedList<Character> list) {
		// TODO Auto-generated method stub
		list.add(map[i][j]);
		if(cnt> max) {
			max= cnt;
		}
		int nx = 0;
		int ny = 0;
		for(int k=0; k<4; k++) {
			nx = i + dirX[k];
			ny = j + dirY[k];
			int flag = 0;
			if(nx>=0&&ny>=0 && nx<r && ny<c) {
				if(list.contains(map[nx][ny])) {	
					flag++;
					continue;
				}
				if(flag==0) {
					dfs(nx,ny,cnt+1,list);
					list.remove(list.size()-1);
				}
			}  
			
			
			
		}
		return;
	}
}

//////////////////////////밑이 되는 코드 .////////////////////

package com.holiday;
import java.util.ArrayList;
import java.util.Scanner;
public class Problem_1987알파벳 {
	static int[] dr = {0,0,-1,1};
	static int[] dc = {-1,1,0,0};
	static int R;
	static int C;
	static int cnt;
	static int answer;
	static ArrayList<Character> list = new ArrayList<>();
 	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		C = sc.nextInt();
		boolean[][] map_check = new boolean[R][C];
		char[][] map = new char[R][C];
		for(int i = 0; i< R; i++)
		{
			String tmp = sc.next();
			for(int j = 0; j < C; j++)
				map[i][j] =tmp.charAt(j);
		}
		cnt = 0;
		answer =0;
		list.add(map[0][0]);
		start(0,0,map);
		System.out.println(answer);
	}
	private static void start(int row, int col, char[][] map) {
		cnt++;
		answer = Math.max(answer, cnt);
		L:for(int k = 0 ; k < 4; k++)
		{
			int mov_row = row + dr[k];
			int mov_col = col + dc[k];
			if(mov_row >= 0 && mov_col >= 0 && mov_row < R && mov_col < C)
			{
				for(int i = 0 ; i< list.size(); i++)
				{
					if(map[mov_row][mov_col] == list.get(i))
						continue L;
				}
				// 겹치는게 없으면 
				list.add(map[mov_row][mov_col]);
				start(mov_row, mov_col, map);
				cnt--;
				list.remove(list.size()-1);
			}
		}
		return;
	}
}

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

문제

문제

출처

ICPC

1987 문제 너무 스트레스받아서 올립니다. 2 코드의 차이가 뭔가요 ??

ty576 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말