백준 1987번 문제

알고리즘 공부를 하다가 이 문제는 자료구조 시간에 배운 DFS를 활용할 수 있는 문제란 것을 알고 따로 문제를 풀어보게 되었다. 이 문제가 왜 DFS 이냐면 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 같은 알파벳이 나오거나 갈 수 있는 길이 없게 된다면 다시 가까운 갈림길로 돌아와 이곳으로 부터 다른 방향으로 다시 탐색을 진행하는 방법이기 때문이다.  또한 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있기 때문에 DFS로 해결 할 수 있다. 

 

또한 이 문제에서 중요한 것은 메모리와 런타임이 제한되어있다는 것이다. 그래서 무작정 단순한 비교문을 썼다가는 아예 런타임 에러가 뜰 수 있다. .. 

일단 내가 쓴 코드이다. 

package sw_samsung;
import java.io.BufferedReader;
import java.util.Scanner;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;

class p1 {
	
	/*int MAX = 1000;
    int front;    
    int rear;    
    static int [] queue;
    public p1() {
        front = rear = 0;    
        queue = new int[MAX]; 
    }
    public boolean queueisEmpty() { 
        return front == rear;
    }
    public boolean queueisFull() {    
        if(rear == MAX-1) {
            return true;
        }else 
            return false;
    }
    public int size() { 
        return front-rear;
    }
    public void push(int value) {
        if(queueisFull()) {
            System.out.println("Queue is Full");
            return;
        }
        queue[rear++] = value; 
    }
    public int pop() {
        if(queueisEmpty()) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int popValue = queue[front++];
        return popValue;
    }
    */
	
	
	static int R, C;
	static boolean[] visit = new boolean[26];
	static int[][] map;
	
	static int[] Xx = { -1, 1, 0, 0 };
	static int[] Yy = { 0, 0, -1, 1 };
	static int result = 0;

	public static void dfs(int x, int y, int count) {
		if (visit[map[x][y]]) { 
			result = Math.max(result, count);
		} else {
			visit[map[x][y]] = true;
			for (int i = 0; i < 4; i++) {
				int dx = x + Xx[i];
				int dy = y + Yy[i];

				if (dx >= 0 && dy >= 0 && dx < R && dy < C) {
					dfs(dx, dy, count + 1);
				}

			}

			visit[map[x][y]] = false;

		}
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		Queue<Integer> queue = new LinkedList<Integer>();
		//int[] testarr;
		//testarr = new int[T];
		
		
		for(int test_case =0  ; test_case < T; test_case++)
		{
			BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(bf.readLine());
			
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			map = new int[R][C];
			
			if(R!=0) {
			for (int i = 0; i < R; i++) {
				String str = bf.readLine();
				for (int j = 0; j < C; j++) {
					map[i][j] = str.charAt(j) - 'A';
				}
			}}
	
			dfs(0, 0, 0);
			queue.offer(result);
			//testarr[test_case] = result;
		
		}
		sc.close();
		
		while(!queue.isEmpty()) {
		for(int test_case=1; test_case<=T;test_case++) {
			
			System.out.print("#"+test_case+"  ");
			System.out.println(queue.poll());
			//System.out.println(testarr[test_case-1]);
			
		}
		}
		queue.clear();
	}
}

중간에 아직 많이 고민한 흔적이 있다. 메모리 활용을 최대한 줄이기 위해 처음에는 동적메모리를 할당하는 방법을 사용하려고 했으나 큐 ( queue) 를 활용하였다. 왜냐하면 이 문제 자체가 한 번의 실행이 아닌 처음에 입력한 숫자만큼 테스트를 해야하기 때문에 알파벳이 많아지고 문자가 길어질 수록 감당이 되지 않기 때문에 큐(queue)를 활용하였다. 

하지만.. 계속 런타임 에러가 났다... 메모리가 크고 실행시간이 길어서란다... 

아직까지 제대로 된 알고리즘 공부를 학교에서 배우지도 따로 공부를 해보지 못해서 이러한 문제는 나중에 보완 할 수 있을 거라고 생각하고 여기까지만 하겠다..