백준 2310 - 어드벤처 게임(Java)

www.acmicpc.net/problem/2310

2310번: 어드벤처 게임

1. 유형

그래프, 구현, 재귀

 

2. 자료구조

- 어레이리스트

 

3. 기능

- 인접리스트 만들기

- E,L,T 조건에 맞게 통과시키기

 

4. 풀이

 

재귀의 매개변수로 소지금, 현재노드를 주고 ELT 조건에 맞게 소지금을 변경해 주면 된다.

 

코드.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int N, fee[];
	static ArrayList<Pair> list[];
	static char type[];
	static boolean flag, visit[];
	static class Pair {
		int node;

		public Pair(int node) {
			// TODO Auto-generated constructor stub
			this.node = node;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		while (true) {
			st = new StringTokenizer(in.readLine());
			N = Integer.valueOf(st.nextToken());
			type = new char[N+1];
			flag = false;
			visit = new boolean[N+1];
			if(N==0)
				break;
			list = new ArrayList[N + 1];
			fee = new int[N+1];
			for (int i = 1; i <= N; i++) {
				list[i] = new ArrayList<>();
			}
			for(int i=1; i<=N; i++) {
				st = new StringTokenizer(in.readLine());
				type[i] = st.nextToken().charAt(0);
				fee[i] =  Integer.valueOf(st.nextToken());
				while(true) {
					int node = Integer.valueOf(st.nextToken());
					if(node==0) break;
					list[i].add(new Pair(node));				
				}
			}
			//탐색
			if(type[1]!='T') {
				visit[1] = true;
				recur(fee[1], 1);
			}
			if(flag) {
				System.out.println("Yes");
			}else
				System.out.println("No");
		}
	}
	static void recur(int myMoney, int curNode) {
		if(flag) return;
		if(curNode == N) {
			flag = true;
			return;
		}
		for(Pair next : list[curNode]) {
			if(visit[next.node]) {
				continue;
			}
			
			if(type[next.node]=='L') {
				if(myMoney>=fee[next.node]) {
					visit[next.node] = true;
					recur(myMoney, next.node);
				}else {
					visit[next.node] = true;
					recur(fee[next.node], next.node);
				}
			}else if(type[next.node]=='T') {
				if(myMoney >= fee[next.node]) {
					visit[next.node] = true;
					recur(myMoney - fee[next.node], next.node);
				}else {
					return;
				}
			}else {
				visit[next.node] = true;
				recur(myMoney, next.node);
			}
			visit[next.node]=false;
		}
	}
}

5. 느낀점

문제는 빠르게 접근했지만 중복체크에서 정말 많이 틀렸다.

T인 경우 소지금이 부족했을 때, 노드에 아예 방문조차 못한다는 것을 다른 조건으로 받아들였다.

또한 1번 노드가 빈방만 인지 T, E인지 모호해서 이런 조건도 있으면 좋을거 같다.