IT Docs

문제 링크 : https://www.acmicpc.net/problem/7569

백준 7576 토마토 문제를 풀고 난 후에 시도한 문제라서 쉬울 거라 생각하고 문제를 접근했다.

7576 토마토는 2차원 문제라면 7569 토마토는 3차원 문제였다.

알고 있는 유형의 문제라서 그런지 너무 쉽게 생각하여 입력 방식에 대해 잘못 구현했다.

첫 시도는 틀렸습니다를 받았다. 문제를 다시 정독한 후 입력 방식을 바꾸고 문제를 해결했다.

구현에 대해서는 어렵지 않았지만 문제를 파악하는데 실수가 있었다.

알고 있는 유형의 문제라도 빠른 해결을 위해 꼼꼼히 읽어보자!!

아래와 같이 구현 소스를 공유합니다.

public class 토마토 {
	public static class Node {
		int x, y, h, s;
		Node(int x, int y, int h, int s) {
			this.x = x;
			this.y = y;
			this.h = h;
			this.s = s;
		}
	}
	public static int X, Y, H, cnt;
	public static int[][][] arr;
	public static boolean[][][] visit;
	public static Queue<Node> que = new LinkedList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] str = br.readLine().split(" ");
		
		Y = Integer.parseInt(str[0]);
		X = Integer.parseInt(str[1]);
		H = Integer.parseInt(str[2]);
		
		arr = new int[X][Y][H];
		visit = new boolean[X][Y][H];
		
		boolean isSuccessed = true;
		
		for (int f = 0; f < H; f++) {
			for (int i = 0; i < X; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < Y; j++) {
					int v = Integer.parseInt(st.nextToken());
					if(v == 0) isSuccessed = false;
					if(v == 1) {
						que.add(new Node(i, j, f, 0));
						visit[i][j][f] = true;
					}
					arr[i][j][f] = v;
				}
			}
		}
		
		if(isSuccessed) {
			System.out.println("0");
		}else {
			bfs();
			
			boolean isCompleted = true;
			
			for (int f = 0; f < H; f++) {
				for (int i = 0; i < X; i++) {
					for (int j = 0; j < Y; j++) {
						int v = arr[i][j][f];
						if(v == 0) isCompleted = false;
					}
				}
			}
			
			if(isCompleted) {
				System.out.println(cnt-1);
			}else {
				System.out.println("-1");
			}
			
		}
	}
	
	public static void bfs() {
		int[] dx = {0, -1, 0, 1, 0, 0};
		int[] dy = {-1, 0, 1, 0, 0, 0};
		int[] dh = {0, 0, 0, 0, -1, 1};
		
		while(!que.isEmpty()) {
			int size = que.size();
			cnt++;
			for (int i = 0; i < size; i++) {				
				Node node = que.poll();
				
				for (int j = 0; j < 6; j++) {
					int xx = node.x + dx[j], yy = node.y + dy[j], hh = node.h + dh[j];
					if(xx < X && yy < Y && hh < H && xx >= 0 && yy >= 0 && hh >= 0) {
						if(!visit[xx][yy][hh] && arr[xx][yy][hh] == 0) {
							visit[xx][yy][hh] = true;
							arr[xx][yy][hh] = node.s + 1;
							que.add(new Node(xx, yy, hh, node.s + 1));
						}
					}
				}
			}
		}
 	}
 }

문제 링크 : https://www.acmicpc.net/problem/5052

처음 전화번호 목록 문제를 접했을 때 이중 포문을 이용하여 시간 초과가 발생했다.

어떤 방법이 있을까 하고 고민할 때 스터디원이 Trie 자료구조를 사용하면 풀 수 있다고 힌트를 주었다.

하지만 Trie 자료구조를 모르고 있었기에 학습하여 문제를 해결하였고 Trie 자료구조를 이용하지 않더라도 풀 수 있는 방법이 있길래 Trie 자료구조를 사용하지 않는 방법으로 문제를 풀어보았다.

아래와 같이 소스를 공유한다.

Trie 자료구조를 이용한 구현

public class 전화번호목록 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for (int e = 0; e < T; e++) {
			int ca = Integer.parseInt(br.readLine());
			List<String> list = new ArrayList<>();
			Trie t = new Trie();
			
			for (int i = 0; i < ca; i++) {
				String word = br.readLine();
				list.add(word);
				t.insert(word);
			}
			
			boolean is = false;
			
			for(String k : list) {
				if(t.contains(k)) {
					is = true;
					break;
				}
			}
			
			sb.append((is == true) ? "NO":"YES").append("\n");
		}
		
        bw.write(sb.toString());
        bw.flush();
        bw.close();
	}
}

public class Trie {
	private TrieNode rootNode;
	
	public Trie() {
		this.rootNode = new TrieNode();
	}
	
	public void insert(String word) {
		TrieNode root = this.rootNode;
		
		for (int i = 0; i < word.length(); i++) {
			root = root.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
		}
		root.setIsLastChar(true);
	}
	
	public boolean contains(String word) {
		TrieNode temp = this.rootNode;
		
		for (int i = 0; i < word.length(); i++) {
			char ch = word.charAt(i);
			TrieNode node = temp.getChildNodes().get(ch);
			
			if(node == null) return false;
			
			temp = node;
		}
		
		if(temp.isLastChar()) {
			if(temp.getChildNodes().isEmpty()) {
				return false;
			}
		}
		
		return true;
	}
	
	public void delete(String word) {
		delete(this.rootNode, word, 0);
	}
	
	public void delete(TrieNode node, String word, int idx) {
		char ch = word.charAt(idx);
		
		if(!node.getChildNodes().containsKey(ch)) throw new Error(word + " : 존재하지 않습니다.");
		
		TrieNode child = node.getChildNodes().get(ch);
		idx++;
		
		if(idx == word.length()) {
			if(!child.isLastChar()) throw new Error(word + " : 존재하지 않습니다.");
			
			child.setIsLastChar(false);
			
			if(child.getChildNodes().isEmpty()) node.getChildNodes().remove(ch);
		}else {
			delete(child, word, idx);
			
			if(!child.isLastChar() && child.getChildNodes().isEmpty()) node.getChildNodes().remove(ch);
		}
	}
	
	public boolean isRootEmpty() {
		return this.rootNode.getChildNodes().isEmpty();
	}
}

public class TrieNode {
	private Map<Character, TrieNode> childNodes = new HashMap<>();
	private boolean isLastChar;
	
	Map<Character, TrieNode> getChildNodes() {
		return this.childNodes;
	}
	
	boolean isLastChar() {
		return this.isLastChar;
	}
	
	void setIsLastChar(boolean is) {
		this.isLastChar = is;
	}
}

Trie 자료구조는 트리 형식으로 문자열을 찾는 자료구조이다.

Trie 자료구조를 이용하지 않은 구현

public class 전화번호목록 {
	public static Comparator<String> compare = new Comparator<>() {

		@Override
		public int compare(String o1, String o2) {
			return o1.compareTo(o2);
		}
		
	};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for (int e = 0; e < T; e++) {
			int c = Integer.parseInt(br.readLine());
			
			List<String> list = new ArrayList<>();
			
			for (int i = 0; i < c; i++) {
				list.add(br.readLine());
			}
			
			Collections.sort(list, compare);
			boolean is = false;
			for (int i = 1; i < c; i++) {
				if(list.get(i).startsWith(list.get(i-1))) {
					is = true;
					break;
				}
			}
			
			System.out.println((is == true) ? "NO":"YES");
		}
	}
}

주어지는 문자들을 정렬하고 startsWith 함수를 이용하여 비교한다.

문제를 푸는 방식이 다양하여 한 가지 문제를 풀더라도 여러 방법으로 풀어 다양한 접근 방식을 습득하려고 노력중이다.

참고 자료

• Trie 자료 구조 : the-dev.tistory.com/3

• blue-boy.tistory.com/189

문제 링크 : https://www.acmicpc.net/problem/16469

소년점프 문제를 처음 접했을때 bfs로 풀 수 있다는 접근 이외에는 아무것도 떠오르지 않았다.

며칠을 생각해도 풀리지 않아 결국 검색해서 힌트를 얻어 문제를 풀 수 있었다.

얻은 힌트를 공유하자면 넉살, 스윙스, 창모 3명의 움직임을 파악할 수 있도록 3개의 배열을 사용하는것이다.

아래의 소스와 같이 구현하여 소년점프 문제를 해결하였다.

public class 소년점프 {
	public static class Node {
		int x, y, s;
		Node(int x, int y, int s) {
			this.x = x;
			this.y = y;
			this.s = s;
		}
	}
	public static int X, Y;
	public static int[][] arr, brr, crr, map, res;
	public static boolean[][] visit;
	public static Queue<Node> que = new LinkedList<>();
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		String[] str = br.readLine().split(" ");
		
		X = Integer.parseInt(str[0]);
		Y = Integer.parseInt(str[1]);
		
		arr = new int[X][Y];
		brr = new int[X][Y];
		crr = new int[X][Y];
		map = new int[X][Y];
		res = new int[X][Y];
		visit = new boolean[X][Y];
		
		for(int i = 0; i < X; i++) {
			String s = br.readLine();
			for (int j = 0; j < Y; j++) {
				int val = Integer.parseInt(String.valueOf(s.charAt(j)));
				if(val == 1)  {
                	// 넉살 이동 배열
					arr[i][j] = -1;
                    // 스윙 이동 배열
					brr[i][j] = -1;
                    // 창모 이동 배열
					crr[i][j] = -1;
                    // 3명의 악당 방문 기록 배열
					map[i][j] = -1;
                    // 3명의 악당이 모두 한 곳에 방문할 수 있는 시간 배열
					res[i][j] = -1;
				}
			}
		}
		
		for(int i = 0; i < 3; i++) {
			String[] f = br.readLine().split(" ");
			int r = Integer.parseInt(f[0])-1;
			int c = Integer.parseInt(f[1])-1;
			search(i, r, c);
		}
		
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < X; i++) {
			for (int j = 0; j < Y; j++) {
            	// res[i][j] != -1 >>>> 벽으로 막혀있지 않는 곳
                // map[i][j] == 3 >>>> 악당 3명 모두 방문한 곳
				if(res[i][j] != -1 && map[i][j] == 3) {
                	// 3명이 한 곳에 다 모이기 위해서는 i,j 위치에 가장 늦게 도착한 악당 기준으로 시간을 체크해야한다.
					res[i][j] = Math.max(Math.max(arr[i][j], brr[i][j]), crr[i][j]);
					if(res[i][j] < min) min = res[i][j];
				}
			}
		}
		
		if(min != Integer.MAX_VALUE) {
			int cnt = 0;
			for (int i = 0; i < X; i++) {
				for (int j = 0; j < Y; j++) {
					if(res[i][j] == min) cnt++;
				}
			}
			
			sb.append(min).append("\n");
			sb.append(cnt);
		}else {
			sb.append(-1);
		}
	
    bw.write(sb.toString());
    bw.flush();
    bw.close();
	}
	
	public static void search(int o, int x, int y) {
		que.add(new Node(x, y, 1));
		visit[x][y] = true;
		map[x][y] += 1;
		bfs(o);
		clear();
	}
	
    // 각 악당의 방문 여부 배열과 방문할 수 있는 Queue 초기화
	public static void clear() {
		visit = new boolean[X][Y];
		que.clear();
	}
	
	public static void bfs(int o) {
		int[] dx = {0, -1, 0, 1};
		int[] dy = {-1, 0, 1, 0};
		
		while(!que.isEmpty()) {
			Node node = que.poll();
			for(int i = 0; i < 4; i++) {
				int xx = node.x + dx[i], yy = node.y + dy[i];
				if(xx < X && yy < Y && xx >= 0 && yy >= 0) {
					if(!visit[xx][yy] && res[xx][yy] != -1) {
						visit[xx][yy] = true;
                        // 악당의 방문 횟수 추가
						map[xx][yy] += 1;
						
                        // 넉살
						if(o == 0) arr[xx][yy] += node.s;
                        // 스윙스
						if(o == 1) brr[xx][yy] += node.s;
                        // 창모
						if(o == 2) crr[xx][yy] += node.s;
						
						que.add(new Node(xx, yy, node.s + 1));
					}
				}
			}
		}
	}
}

이것이 코딩테스트다 118P 구현 문제

문제 : 게임 개발

풀이 시간 40분, 시간 제한 1초, 메모리 제한 128MB

현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한곳을 바라본다.
맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로 부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다.
캐릭터의 움직임을 설정하기 위해 정해 놓은 메뉴얼은 이러하다.

     1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
     2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한칸을 전진한다.
        왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
     3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한칸 뒤로 가고 1단          계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

현민이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다.
메뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

입력 조건
     1. 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (N >= 3, M <= 50)
     2. 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방항 d가 각각 서로 공백으로 구분하여 주어진다.
        방향 d의 값은 다음과 같다. 
           - 0 : 북쪽
           - 1 : 동쪽
           - 2 : 남쪽
           - 3 : 서쪽
     3. 셋째 줄부터 맵이 육지인지 바다인지 입력한다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽          부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어있다.
           - 0 : 육지
           - 1 : 바다
     4. 처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.

출력 조건
     1. 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

입력 예시

4 4        # 4 X 4 맵 생성
1 1 0     # (1, 1)에 북쪽(0)을 바라보고 서 있는 캐릭터
1 1 1 1   # 첫 줄은 모두 바다
1 0 0 1   # 둘째 줄은 바다/육지/육지/바다
1 1 0 1   # 셋째 줄은 바다/바다/육지/바다
1 1 1 1   # 넷째 줄은 모두 바다

출력 예시
3

처음 이코테의 게임 개발 문제를 접했을 때 게임 캐릭터가 서있는 위치를 기준으로 육지를 카운팅 하면 문제가 해결 될것이라 생각했었다. 

위와 같이 생각한 이유는 단순 bfs로 문제의 메뉴얼을 만족한다고 생각했다.

반 시계 방향으로 돌면서 가보지 않은 육지로 이동하고 네 방향 모두 가본 육지라면 뒤로 한칸 간다는 메뉴얼을 분석해보면, 

1. 반시계 방향으로 회전 : 정답을 도출하는데 방향은 중요하지 않다고 생각했다. 정답은 캐릭터가 육지로 이동할 수 있는 칸의 개수이다.
2. 네 방향 모두 가본 칸이거나 바다로 되어있는 칸일 경우 뒤로 한칸 이동 : 캐릭터의 뒤 칸이 바다일 경우 멈출 것이고 바다가 아니면 뒤로 한칸 물러나도 이미 가본 칸이기 때문에 카운팅이 되지 않는다. 그래서 뒤로 갈 수 있는 칸이라면 이미 지나왔던 칸이기 때문이다.

위의 두가지 이유 때문에 단순 bfs로 이동할 수 있는 칸을 카운팅하는 로직을 구현하여 예제 입력에 대한 올바른 출력 예제를 도출하였다.

하지만 구현한 로직을 예제 외의 입력 값으로 테스트 할만한 사이트나 예제가 없었다.

단순 bfs는 로직은 공유하지 않겠다. 그래서 조건을 충족하는 로직으로 다시 문제를 풀었다. 

단순 bfs로 풀수 없는 예제나 위의 2가지 이유가 안되는 이유가 있다면 댓글로 남겨주시면 감사하겠습니다.
여러분의 공유가 큰 도움이 되어 개발자를 성장 시킵니다!

public class 게임개발 {
	public static class Node {
		int x, y, d;
		Node(int x, int y, int d) {
			this.x = x;
			this.y = y;
			this.d = d;
		}
	}
	public static int N, M, cnt;
    // 인접행렬 이용
	public static int[][] arr;
	public static boolean[][] visit;
    // 서남동북으로 기본값을 세팅, 북쪽(0)을 기준으로 왼쪽으로 회전
	public static int[] dx = {0, 1, 0, -1};
	public static int[] dy = {-1, 0, 1, 0};
	public static Queue<Node> que = new LinkedList<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] str = br.readLine().split(" ");
		
		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);
		
		arr = new int[N][M];
		visit = new boolean[N][M];
		
		String[] location = br.readLine().split(" ");
		
		int x = Integer.parseInt(location[0]);
		int y = Integer.parseInt(location[1]);
		int d = Integer.parseInt(location[2]);
		// 플레이어의 최초 위치와 방향 지정
		que.add(new Node(x, y, d));
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		bfs();
		
		bw.write(Integer.toString(cnt));
		bw.flush();
		bw.close();
	}
	
	public static void bfs() {
		while(!que.isEmpty()) {
			Node node = que.poll();
			int isVisit = 1;
            // 플레이어 회전
			for (int i = 0; i < 4; i++) {
            	// 플레이어가 바라보는 위치에서 왼쪽 방향을 바라보도록 위치 지정
				int idx = (node.d + i) % 4;
				int xx = node.x + dx[idx], yy = node.y + dy[idx];
				if(xx < N && yy < N & xx >= 0 && yy >= 0) {
					if(!visit[xx][yy] && arr[xx][yy] != 1) {
						visit[xx][yy] = true;
						cnt++;
						que.add(new Node(xx, yy, idx));
					}else {
						isVisit++;
					}
				}
			}
			// 4방향 모두 이동 불가 시
			if(isVisit == 4) {
				int idx = (node.d+2)%4;
				int xx = node.x + dx[idx];
				int yy = node.y + dy[idx];
				if(arr[xx][yy] != 1) {
					que.add(new Node(xx, yy, node.d));
				}else {
					break;
				}
			}			
		}
	}
}

공유 한 소스의 핵심은 4방향으로 움직이고 4방향 모두 이동이 불가할때 뒤로 한칸 물러서는 로직이다.

움직이는 방향을 설정할때 서남동북으로 방향을 설정하였다.

public static int[] dx = {0, 1, 0, -1};
public static int[] dy = {-1, 0, 1, 0};

bfs가 동작할때 현재 위치에서 서남동북 순으로 순환한다.

캐릭터의 위치가 북쪽(0)이라면 왼쪽을 바라보도록 dx, dy의 0번째(캐릭터가 바라보는 방향의 값을 활용) 위치를 서쪽으로 지정하였다.

int idx = (node.d + i) % 4;

서남동북 순으로 이동이 되지 않을때 이동하지 못한 회수를 카운팅 하였다.

cnt++;

4방향 모두 이동이 불가할때 현재 위치 값을 +2 더해주면 캐릭터의 뒤 칸 위치 값을 찾을 수 있다. 

0 북, 1 동, 2 남, 3 서 일때 캐릭터가 바라보는 위치가 북(0)에서 +2를 더해주면 남(2)가 되기 때문이다.

if(isVisit == 4) {
    int idx = (node.d+2)%4;
    int xx = node.x + dx[idx];
    int yy = node.y + dy[idx];
    if(arr[xx][yy] != 1) {
        que.add(new Node(xx, yy, node.d));
    }else {
        break;
    }
}

이런 로직을 구현했을때 이동 해야할 방향, 서남동북을 기준으로 아래와 같이 움직여 정답을 찾을 수 있었다.

최초 위치 -> x : 1, y : 1, 방향 : 0(서)
이동 위치 -> x : 1, y : 2, 방향 : 2(동)
이동 위치 -> x : 2, y : 2, 방향 : 2(동)
이동 위치 -> x : 1, y : 2, 방향 : 1(남)