[14500] 테트로미노 in Java

 

 

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

---

백트래킹을 사용하여

폴리오미노 모양을 만들어주었던 문제

 

이때 방문했던 지점에서 깊이가 4가 되기전까지는

무조건 상하좌우 방향을 계속해서 탐색해줘야한다.

 

그래서 dfs 내에서는 3중 for문을 돌려야함.

 

 

package week5;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class n14500 {
    static int n,m;
    static int[][] map;
    static int[] dxs= {-1,1,0,0};
    static int[] dys= {0,0,-1,1};
    static int answer;
    static boolean[][] visited;
    static ArrayList<Point> queue;
    
    static class Point{
        int x,y;
 
        public Point(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
        
    }
    
    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];
        answer=0;
        visited=new boolean[n][m];
        queue=new ArrayList<>();
        
        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;
                queue.add(new Point(i,j));
                dfs(1,map[i][j]);
                visited[i][j]=false;
                queue.remove(0);
            }
        }
        System.out.println(answer);
    }
 
    public static void dfs(int cnt, int sum) {
        if(cnt==4) {
            answer=Math.max(answer, sum);
            return;
        }
        for (int c = 0; c < queue.size(); c++) {
            Point p=queue.get(c);
            for (int i = 0; i < 4; i++) {
                int nx=p.x+dxs[i];
                int ny=p.y+dys[i];
                if(canGo(nx,ny) && !visited[nx][ny]) {
                    visited[nx][ny]=true;
                    queue.add(new Point(nx,ny));
                    dfs(cnt+1,sum+map[nx][ny]);
                    visited[nx][ny]=false;
                    queue.remove(queue.size()-1);
                }
                
            }
        }    
    }
 
    public static boolean canGo(int x, int y) {
        return x>=0 && x<n && y>=0 && y<m;
    }
}
 

 

package week5;

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

public class n14500 {
	static int n,m;
	static int[][] map;
	static int[] dxs= {-1,1,0,0};
	static int[] dys= {0,0,-1,1};
	static int answer;
	static boolean[][] visited;
	static ArrayList<Point> queue;
	
	static class Point{
		int x,y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
	}
	
	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];
		answer=0;
		visited=new boolean[n][m];
		queue=new ArrayList<>();
		
		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;
				queue.add(new Point(i,j));
				dfs(1,map[i][j]);
				visited[i][j]=false;
				queue.remove(0);
			}
		}
		System.out.println(answer);
	}

	public static void dfs(int cnt, int sum) {
		if(cnt==4) {
			answer=Math.max(answer, sum);
			return;
		}
		for (int c = 0; c < queue.size(); c++) {
			Point p=queue.get(c);
			for (int i = 0; i < 4; i++) {
				int nx=p.x+dxs[i];
				int ny=p.y+dys[i];
				if(canGo(nx,ny) && !visited[nx][ny]) {
					visited[nx][ny]=true;
					queue.add(new Point(nx,ny));
					dfs(cnt+1,sum+map[nx][ny]);
					visited[nx][ny]=false;
					queue.remove(queue.size()-1);
				}
				
			}
		}	
	}

	public static boolean canGo(int x, int y) {
		return x>=0 && x<n && y>=0 && y<m;
	}
}