링크

14500 테트로미노

문제

풀이

처음에 bfs를 통해 문제를 해결했다
그러나 마지막 예제가 통과가 안된다. 안되는 이유는 사진에서의 분홍색 ㅗ ㅜ ㅓ ㅏ 이 모양을 bfs로는 만들 수 없다. 그래서 나는 1 2 3 4는 탐색을 하고 ㅗ ㅜ ㅓ ㅏ는 따로 코딩해서 최댓값을 찾았다.
1. 완탐한다
2. ㅗㅜㅏㅓ와 같은 탐색으로는 못만드는 모양을 따로 빼서 코딩한다.

코드

처음 실패한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node{
	int x;
	int y;
	int dept;
	int sum;
	
	public Node(int x, int y, int dept, int sum) {
		this.x = x;
		this.y = y;
		this.dept = dept;
		this.sum = sum;
	}
}


public class Main {
	public static int max = 0;
	public static int[][] map;
	// 세로 가로 방향(0:위, 1:오른쪽, 2:아래, 3:왼쪽)
	public static boolean[][][] visited;
	public static Stack<Node> stack;
	
	public static int[] dx = {1, 0, -1, 0};
	public static int[] dy = {0, 1, 0, -1};
	
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] arr = br.readLine().split(" ");
		int n = Integer.parseInt(arr[0]);
		int m = Integer.parseInt(arr[1]);
		
		map = new int[n][m];
		
		for(int i=0;i<n;i++) {
			arr = br.readLine().split(" ");
			
			for(int j=0;j<arr.length;j++) {
				map[i][j] = Integer.parseInt(arr[j]);
			}
		}
		

		// bfs로 하려고 했지만 실패한 코드
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map[i].length;j++) {
				visited = new boolean[map.length][map[0].length][4];
//				System.out.println("startX = " + i + " startY = " + j);
				bfs(i, j);
//				System.out.println("-----------------------");
			}
		}
		
		System.out.println(max);
		
	}
	
	
	public static void bfs(int x, int y) {
		Queue<Node> queue = new LinkedList<>();
		queue.add(new Node(x, y, 1, map[x][y]));
		
		while(!queue.isEmpty()) {
			Node currentNode = queue.poll();
						
			for(int i=0;i<4;i++) {
				int newX = currentNode.x + dx[i];
				int newY = currentNode.y + dy[i];
				int step = currentNode.dept;
				int sum = currentNode.sum;
				
				// 벗어나거나 방문했으면 움직이지 않기
				if(newX < 0 || newY < 0 || newX >= map.length || newY >= map[0].length || visited[newX][newY][i]) continue;
				// 4번 움직였으면 움직이지 않기
				if(step == 4) {
					max = Math.max(max, sum);
					continue;
				}
				
				
//				System.out.println("x = " + currentNode.x + " y = " + currentNode.y);
//				System.out.println("newX = " + newX + " newY = " + newY + " sum = " + sum +" dept = " + step);
				
				visited[newX][newY][i] = true;
				queue.add(new Node(newX, newY, step+1, sum+map[newX][newY]));
				
				
				
			}
		}
		
		
		
	}
	
	
	
}

성공한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node{
	int x;
	int y;
	int dept;
	int sum;
	
	public Node(int x, int y, int dept, int sum) {
		this.x = x;
		this.y = y;
		this.dept = dept;
		this.sum = sum;
	}
}


public class Main {
	public static int max = 0;
	public static int[][] map;
	public static boolean[][] visited;
	public static Stack<Node> stack;
	
	public static int[] dx = {1, 0, -1, 0};
	public static int[] dy = {0, 1, 0, -1};
	
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] arr = br.readLine().split(" ");
		int n = Integer.parseInt(arr[0]);
		int m = Integer.parseInt(arr[1]);
		
		map = new int[n][m];
		
		for(int i=0;i<n;i++) {
			arr = br.readLine().split(" ");
			
			for(int j=0;j<arr.length;j++) {
				map[i][j] = Integer.parseInt(arr[j]);
			}
		}
		
		
		
		//백트래킹으로 접근
		
		visited = new boolean[map.length][map[0].length];
		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map[0].length;j++) {
				visited[i][j] = true;
//				System.out.println("i = " + i + " j = " + j);
				dfs(i, j, 1, map[i][j]);
				visited[i][j] = false;
				// ㅗ, ㅜ, ㅏ, ㅓ와 같은 친구들 따로 탐색
				checkException(i, j);
			}			
		}
		
		
		System.out.println(max);
		
	}
	
	public static void dfs(int x, int y, int dept, int sum) {
		if(dept == 4) {
			max = Math.max(sum, max);
//			System.out.println("------------------------");
			return;
		}
		
		for(int i=0;i<4;i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			
			if(newX < 0 || newY < 0 || newX >= map.length || newY >= map[0].length || visited[newX][newY]) continue;
			
//			System.out.println("newX = " + newX + " newY = " + newY + " dept = " + (dept + 1) + " sum = " + (sum + map[newX][newY]));
			
			visited[newX][newY] = true;
			dfs(newX, newY, dept+1, sum + map[newX][newY]);
			visited[newX][newY] = false;
			
		}
			
		
		
	}
	
	
	public static void checkException(int x, int y) {
		//ㅗ
		if(x+1 < map.length && y-1 >= 0 && y+1 < map[0].length) {
			int sum = map[x][y] + map[x+1][y] + map[x+1][y-1] + map[x+1][y+1];
			max = Math.max(max, sum);
		}
		
		//ㅜ
		if(x-1 >= 0 && y-1 >= 0 && y+1 < map[0].length) {
			int sum = map[x][y] + map[x-1][y] + map[x-1][y-1] + map[x-1][y+1];
			max = Math.max(max, sum);
		}
		
		//ㅏ
		if(x+1 < map.length && x-1 >= 0 && y-1 >= 0) {
			int sum = map[x][y] + map[x][y-1] + map[x+1][y-1] + map[x-1][y-1];
			max = Math.max(max, sum);
		}
		
		
		//ㅓ
		if(x-1 >= 0 && x+1 < map.length && y+1 < map[0].length) {
			int sum = map[x][y] + map[x][y+1] + map[x-1][y+1] + map[x+1][y+1];
			max = Math.max(max, sum);
		}
	}
	
	
	
}