백준 14500 JAVA

문제 유형

• DFS

문제 접근

• 답
  • 4칸으로 가질 수 있는 최대 값(대각선 불가)
• 주어지는 정보
  • 맵 크기 N*M = 250000
  • 탐색 범위 5*4 = 20
    • 테트로미노 종류 * 회전(4방향) = 20
  ⇒ 250000*20 = 5,000,000이므로 완전탐색 가능
• DFS vs BFS
  • BFS
    • BFS는 ㅗ 모양을 만들기 적절치 않음(visit 기록할 때, 타이밍이 안맞음)
  • DFS
    • 테트로미노 모양의 탐색에 있어 전부 대응 가능
  • ⇒ DFS

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


public class Main {
    public static int N,M;
    public static int[][] map;
    public static boolean[][] visited;
    public static int[][] move = {{0,1},{1,0},{0,-1},{-1,0}};
    public static int value = 0;
    
    public static void dfs(int x, int y, int cnt, int result)
    {
        if(cnt == 4)
        {
            value = Math.max(value, result);
            return;
        }
        
        for(int i = 0; i<4; i++)
        {
            int moveX = x + move[i][0];
            int moveY = y + move[i][1];
            
            if(moveX < 0 || moveX >= M || moveY < 0 || moveY >= N || visited[moveY][moveX] == true)
            {
                continue;
            }
            
            if(cnt == 2)
            {
                visited[moveY][moveX] = true;
                dfs(x,y,cnt+1,result+map[moveY][moveX]);
                visited[moveY][moveX] = false;
            }
            
            visited[moveY][moveX] = true;
            dfs(moveX,moveY, cnt+1, result + map[moveY][moveX]);
            visited[moveY][moveX] = false;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        visited = new boolean[N][M];
        
        for(int i = 0; i<N; i++)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<M; j++)
            {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i = 0; i<N; i++)
        {
            for(int j = 0; j<M; j++)
            {
                visited[i][j] = true;
                dfs(j,i,1,map[i][j]);
                visited[i][j] = false;
            }
        }
        
        System.out.println(value);
        
    }
}

 

 

나의 틀린 답안

문제 접근

• BFS
  • ㅗ모양의 탐색을 진행하기가 어려웠음

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

class XY
{
    public int x;
    public int y;
    public int cnt;
    public int value;
    
    public XY(int x, int y, int cnt, int value)
    {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
        this.value = value;
    }
}

public class HelloWorld {
    public static int N,M;
    public static int[][] map;
    public static boolean[][] visited;
    public static int[][] move = {{0,1},{1,0},{0,-1},{-1,0}};
    public static int result = 0;
    
    public static void bfs(int x, int y)
    {
        boolean[][] visited2 = new boolean[N][M];
        Queue<XY> q = new LinkedList<>();
        q.add(new XY(x,y,1,map[y][x]));
        
        while(!q.isEmpty())
        {
            XY cur = q.peek();
            q.remove();
            
            if(cur.cnt == 4)
            {
                result = Math.max(result, cur.value);
                continue;
            }
            
            
            for(int i = 0; i<4; i++)
            {
                int moveX = cur.x + move[i][0];
                int moveY = cur.y + move[i][1];
                
                if(moveX < 0 || moveX >= M || moveY < 0 || moveY >= N || visited2[moveY][moveX] == true || visited[moveY][moveX] == true)
                {
                    continue;
                }

                int value = cur.value + map[moveY][moveX];
                q.add(new XY(moveX,moveY,cur.cnt+1,value));
            }
            visited2[cur.y][cur.x] = true;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        visited = new boolean[N][M];
        
        for(int i = 0; i<N; i++)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<M; j++)
            {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i = 0; i<N; i++)
        {
            for(int j = 0; j<M; j++)
            {
                visited[i][j] = true;
                bfs(j,i);
            }
        }
        
        System.out.println(result);
        
    }
}