백준 1987; java

https://www.acmicpc.net/problem/1987

1987번: 알파벳

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static int[][] A;
	static boolean[][] visit;
	static List list;
	static int R, C, max;
	//사방위 
	static int[] row= {-1, 0, 1, 0};
	static int[] col= {0, 1, 0, -1};
		
	public static void func(int r, int c, List<Integer> listt) {
		if(!listt.contains(A[r][c])) {
			listt.add(A[r][c]);

			if(listt.size()>max) {
				max=listt.size();
			}
			for(int i=0;i<4;i++) {
				int nr=r+row[i];
				int nc=c+col[i];
				if(nr>=0 && nr<R && nc>=0 && nc<C) {
					func(nr, nc, listt);
				}
			}
			listt.remove(listt.size()-1);
		}
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		R=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		
		A=new int[R][C];
		visit=new boolean[R+1][C+1];
		for(int i=0;i<R;i++) {
			String line=br.readLine();
			for(int j=0;j<C;j++) {
				A[i][j]=line.charAt(j)-'A';
			}
		}

		list=new ArrayList<Integer>();
		func(0, 0, list);
		System.out.println(max);
	}

}

 

-

구글링해서 푼 문제

구글링한 답 이해는 대충 가는데 완벽하게 이해한 것은 아님.. 

다른 사람들이 푼 방법이 더 좋은 풀이방법임을 아는데,, 리스트 써서 꾸역꾸역 풀었음 ㅋ 똥고집 ㅋ 메모리 비효율 오짐!

 

---

import java.util.*;
import java.io.*;

public class Main {
	static int R, C, result=0;
	static int[][] map;
	static boolean[] visited;
	static int[] row= {0,0,1,-1};
	static int[] col= {1,-1,0,0};
	
	public static void dfs(int r, int c, int cnt) {//r,c 현재 위치/cnt 여태까지 온 길 개수
		visited[map[r][c]]=true;
		if(cnt+1>result) {
			result=cnt+1;
		}
		for(int i=0;i<4;i++) {
			int nr=r+row[i];
			int nc=c+col[i];
			if(nr<0||nr>=R||nc<0||nc>=C)	continue;
			if(!visited[map[nr][nc]]) {
				dfs(nr, nc, cnt+1);
				visited[map[nr][nc]]=false;
			}
		}
	}
	
	public static void main(String[] args)throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String[] str=br.readLine().split(" ");
		R=Integer.parseInt(str[0]);
		C=Integer.parseInt(str[1]);
		map=new int[R][C];
		visited=new boolean[26];
		for(int i=0;i<R;i++) {
			String temp=br.readLine();
			for(int j=0;j<C;j++) {
				map[i][j]=temp.charAt(j)-'A';
			}
		}
		dfs(0, 0, 0);
		System.out.println(result);
	}
}

- 두 번째 풀이 방법

인데 또 visited[][]=false해주는 거 틀렸다. 나는 왕 바보.. 

 

런타임 단축~b