WantAirpod

https://programmers.co.kr/learn/courses/30/lessons/42895

문제풀이

• dfs를 통해 모든 경우의 수를 탐색
  • Number가 5,55,555 증가하는 연산

int tmpN = 0;
tmpN = tmpN * 10 + N;

코드

class Solution {
       int answer;
    public int solution(int N, int number) {
        //모든 최솟값이 8보다 커서 dfs가 return 되는 경우는 답이 -1
        answer = -1;
        
         DFS(N, number, 0, 0);
        
        return answer;
    }
    
    public void DFS(int N, int number, int sum, int count){
        if(count > 8) return;
        
        if(sum == number){
            if(count < answer || answer == -1) answer = count;
            return;
        }
        //새로운 DFS를 탈 때 tmpN을 초기화시켜줌으로써 N, NN, NNN 등을 탐색할 수 있다
        int tmpN = 0;
        for(int i=1; i<9; i++){
            tmpN = tmpN*10 + N;
            DFS(N, number, sum+tmpN, count+i);
            DFS(N, number, sum-tmpN, count+i);
            DFS(N, number, sum*tmpN, count+i);
            DFS(N, number, sum/tmpN, count+i);
        }
        
    }
}

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

문제

풀이

• bfs로  w 단지와 b단지를 각각 탐색해서 제곱해서 더해줬다.
• bfs로 각각 돌아도 효율성엔 문제가 없다. O(N+N)
• visit[] 배열로 갔던 곳은 동시에 체크줬다.

삽질ㅅㅂ

맞게 풀었는데 자꾸 런타임 에러(ArrayIndexOutOfBounds)가 뜸.

가로 크기N, 세로크기M이었다.

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

문제

• N과 K과 주어진다.
  • N은 단어, K는 아는 단어이다.
  • 아는 단어를 6개로 지정했을 때 N개의 단어를 몇개 배울 수 있는지 최대 갯수를 출력한다.

풀이

• 아는 단어 중 "anta", "tica"는 반드시 들어간다. 
  
  • "a", "n", "t", "i", "c" 5개의 단어이다.
    • 즉 K가 5이하로 주어지면 배울수 있는 단어는 없다.
    • K=26 이면 모든 단어 가능하다.

코드

• 기본적인 a, n, t, i, c 체크 해주기

 static void beforeCheck(){
        //'a','n','t','i','c'
        alpha2['a' - 'a']  = true;
        alpha2['n' - 'a']  = true;
        alpha2['t' - 'a']  = true;
        alpha2['i' - 'a']  = true;
        alpha2['c' - 'a']  = true;
    }

• dfs 설계
  • cnt == k 일 때 즉, 배울수 있는 단어를 최대로 배운다.
  • 배울 수 있는 단어를 체크한 뒤 가능여부의 max 값을 가져온다.

 static void dfs(int start ,int cnt){
        if(cnt == k){
            int possible = 0 ;
            for(int i = 0 ; i < n; i++){
                boolean flagTrue = true;
                for(int j = 0 ; j < arr[i].length() ; j++){
                    if(!alpha2[arr[i].charAt(j)-'a']){
                        flagTrue = false;
                        break;
                    }
                }
                if(flagTrue == true){
                    possible++;
                }
            }
            max = Math.max(max,possible);
            return ;
        }


        for(int i = start ; i <=26 ; i++){
            if(!alpha2[i]){
                alpha2[i] = true;
                dfs(i,cnt+1);
                alpha2[i] = false;
            }
        }

    }

• 특정 단어 (가운데 단어만 빼서) 검사해서 효율성 올리기

 for(int i = 0 ; i < n ; i ++){
                String tempStr = br.readLine();
                arr[i] = tempStr.substring(4,tempStr.length()-4);
            }
            k  = k - 5;
            beforeCheck();
            dfs(0,0);
            System.out.println(max);
}

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

문제

• M x N 상자가 주어진다.
• 0 : 익지 않은 토마토
• 1 : 익은 토마토
• -1 :  토마토가 없는 칸

풀이

• 퍼져나가므로 bfs가 더 맞을 것 같다.

bfs 구현

  while (!q.isEmpty()) {

            Pair now = q.poll(); // 큐의 맨앞 
            int nowx = now.x;  //현재 토마토 x값
            int nowy = now.y;  //현재 토마토 y값 
            for (int i = 0; i < 4; i++) {
                int nextX = nowx + dx[i];
                int nextY = nowy + dy[i];

                //범위 밖 패스
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }
                
                if (arr[nextX][nextY] != 0) {
                    continue;
                }
                //다음값 = 현재 일수 + 1
                arr[nextX][nextY] = arr[nowx][nowy] + 1;
                q.add(new Pair(nextX, nextY));
            }
        }

답 도출

• 토마토 상자에서 가장 큰 숫자를 출력
• 토마토 상자에 만약 0이 있다면 (익지 못한 상황) -1 출력 종료

  int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 0) {
                    //토마토가 모두 익지 못한 상황이라면 -1 을 출력한다.
                    System.out.println(-1);
                    return;
                }
                max = Math.max(max, arr[i][j]);
            }
        }
        //그렇지 않다면 최대값을 출력한다.
        System.out.println(max - 1);

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

문제

• N x M 사다리가 주어진다. N은 세로선, M은 가로점선이다. 위는 N=5, M=6이다.
• H는 6이다. (가로실선을 놓아 연결할 수 있는 최대 갯수)

• 초록선은 세로선이며, 점선은 가로선이다. 가로선은 인접한 두 세로선사이를 연결해야한다. 단, 두 가로선이 연속하거나 서로 접하면 안된다.

• 1번말은 3번으로 갔고, 2번말은 2번으로 갔다.
• 사다리를 가로선에 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때 i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해 추가해야하는 가로선 갯수의 최소값을 구하는 프로그램을 작성하시오.

입력 예시	설명
	가로선의 정보는 a, b로 주어진다. b번 세로선과 b+1 세로선을 a번 점선 위치에서 연결했는의미이다. ex) 5 1 : 1번과 2번 세로선을 5번 가로선에서 연결한다. 2 3 : 3번과 4번 세로선을 3번 가로선에서 연결한다.

출력

• i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최소값을 출력한다. 만약 정답이 3보다 크면 -1을 출력한다. 또 불가능한 경우에도 -1을 출력한다.

 풀이방법

• 당연히 최소라는 말이 많이 나와 bfs로 접근했지만 시간초과 뜸.
• dfs로 접근
• check 함수 생성 (가로선을 그을 때 마다 가능한지 여부 체크)
• 모든 경우에 가로선을 하나 씩 늘려감

Check 함수

• 세로줄을 검사하면서 1을 만나면 우측으로(y++), 2를만나면 좌측으로(y--) 해준다.
• 해당 말의 결과와 숫자가 같으면 true 해주고 계속 다른 말 검사, 해당 말의 결과와 숫자가 다르면 바로 false return

public static boolean check(){
        for(int i =0  ; i < n ; i++){ 
            int x = 1, y = i;  // 가로줄1번부터 시작, y는 말
            for(int j = 0 ; j < h ; j++){
                if(map[x][y] == 1) {  //만약 해당 칸이 1이면 우측으로 이동 = y++
                    y++;
                }
                else if(map[x][y] ==2){
                    y--;   //만약 해당 칸이 2면 왼쪽으로 이동 y--;
                }
                x++; //만약 해당 칸에 가로선이 없으면 아래로 이동
            }
            if(y != i) return false; // 결국 해당 말이 결과가 다르다면 바로 false
        }
        return true;
    }​

dfs 부분

• 가로선을 그을 수 있는 곳 (=map[i][j] = 0 && map[i][j+1] ==0 인곳)에 모두 가로선을 그어준다.
• 가로선을 긋고 바로 check해준다. 되면 해당 count값을 반환 안되면, 가로선을 그을 수 있을 만큼 계속 그어준다.

 public static void dfs(int x, int count){
        if(answer < count) return ;  
        else{
            if(check()){
                answer = count;
                return;
            }
        }
        for(int i = x ; i < h + 1 ; i++){
            for (int j = 1; j < n ; j++){
                if(map[i][j] == 0 && map[i][j+1] ==0){
                    map[i][j] = 1;
                    map[i][j+1] = 2;
                    dfs(i,count+1);
                    map[i][j] = map[i][j+1] = 0 ;
                }
            }
        }

    }

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

문제 해석

1. NxM 미로가 있다.
2. U, R, D, L 명령에 따라 이동한다.
3. 탈출 가능한 칸을 Count 해준다.
   1. 탈출 가능이란 : 그 칸에서 이동을 시작해서 칸에 적힌대로 이동 했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

풀이

• DFS를 이용해서 푼다. 
• 방문 처리가 중요하다.
  • 처음 방문 한 곳이면서 탈출 가능하면 Count++해준다.
  • 처음 방문 한 곳이 아니면 카운트 해주지 않는다. 즉, 이미 탈출 가능한 경로를 계속해서 저장해야 한다.(DP)

코드

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

public class Main {

    static int[][] map, visited;
    static boolean[] successCheck;
    static int N, M, num = 1, ans = 0;
    static int[][] dt = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    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 int[N][M];
        successCheck = new boolean[N * M + 1];
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                char c = input.charAt(j);
                if (c == 'U') map[i][j] = 0;
                else if (c == 'R') map[i][j] = 1;
                else if (c == 'D') map[i][j] = 2;
                else map[i][j] = 3;
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visited[i][j] != 0) continue;
                dfs(i, j, 0);
                num++;
            }
        }

        System.out.println(ans);
        br.close();
    }

    public static void dfs(int x, int y, int count) {
		//만약 처음 탈출했다면.
        if (check(x, y)) {
            successCheck[num] = true;
            ans += count;
            return;
        //만약 처음 탈출이 아니라면
        } else if (visited[x][y] != 0) {
            if (successCheck[visited[x][y]]) {
                successCheck[num] = true;
                ans += count;
            }
            return;
        }

        visited[x][y] = num; //visit 체크해주기
        dfs(x + dt[map[x][y]][0],  y + dt[map[x][y]][1], count + 1); // 방향 별로 넣어주기
    }

	//탈출조건 체크
    public static boolean check(int x, int y) {
        return x < 0 || x >= N || y < 0 || y >= M;
    }
}

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

문제

• N x M 배열이 주어진다.
• 배열안에는 구멍('0'), 빨간구슬('R'), 파랑구슬('B')가 주어진다.
• 구슬은 중력을 이용해서 이리 저리 굴려야 한다.
  • 이리저리 = 왼쪽, 오른쪽, 위쪽, 아래쪽 기울이기
• 빨간색 구슬이 구멍이 빠지면 성공이다.
  • 조건1) 빨간 구슬과 파란 구슬이 같이 빠지면 실패
  • 조건2) 빨간 구슬과 파란 구슬은 같은 칸에 있으면 안된다.
  • 조건3) 10번 이하로 빼내야 한다.

풀이

• 빨간 구슬과 파란 구슬은 동시에 관리해야한다.
• 바깥 행과 열은 벽('#)으로 막혀있어서 범위를 체크해줄 필요가 없다.
• 만약 같은 칸에 있을 경우!!
  • 빨간 구슬과 파란 구슬의 각각의 이동거리를  계산하여 더 많이 이동한 쪽을 이전 위치 한 칸 돌려준다.

주요 메서드

• 매개변수
  • r : 현재 x좌표
  • c : 현재 y좌표
  • dist : 움직인 거리
  • d : 방향(4방향)

   private static Move move (int r, int c, int dist, int d){
        int rr =r, cc= c;
        if (graph[rr+dx[d]][cc+dy[d]] != '#')
        {
            rr = rr + dx[d];
            cc = cc + dy[d];
            dist ++;
        }
        return new Move(rr,cc,dist);
    }

• 빨간 구슬과 파란 구슬이 같은 칸에 있을 경우

 // 빨간 구슬과 파란 구슬이 같은 칸에 있을 경우
    if (nRed.r == nBlue.r && nRed.c == nBlue.c) {
        // 빨간 구슬이 더 많이 이동했을 경우
        if(nRed.dist> nBlue.dist) {
            // 이전 위치로
            nRed.r -= dx[d];
            nRed.c -= dy[d];
        } else {
            nBlue.r -= dx[d];
            nBlue.c -= dy[d];
        }
    }

• bfs 로직

 while(!q.isEmpty()) {

            int size = q.size();
            while(size-- > 0) {
                Turn now = q.poll();

                // 4방으로 장난감을 기울여보자.
                for (int d = 0; d < 4; d++) {
                    // 빨간 구슬 이동
                    nRed = move(now.Rr, now.Rc, 0, d);
                    // 파랑 구슬 이동
                    nBlue = move(now.Br, now.Bc, 0, d);

                    // 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패
                    if(graph[nBlue.r][nBlue.c] == 'O') continue;
                    // 빨간 구슬만 구멍에 빠질 경우
                    if(graph[nRed.r][nRed.c] == 'O') {
                        return 1;
                    }

                    // 빨간 구슬과 파란 구슬이 같은 칸에 있을 경우
                    if (nRed.r == nBlue.r && nRed.c == nBlue.c) {
                        // 빨간 구슬이 더 많이 이동했을 경우
                        if(nRed.dist> nBlue.dist) {
                            // 이전 위치로
                            nRed.r -= dx[d];
                            nRed.c -= dy[d];
                        } else {
                            nBlue.r -= dx[d];
                            nBlue.c -= dy[d];
                        }
                    }

                    // 이미 시도해봤던 상태라면 pass
                    if(visit[nRed.r][nRed.c][nBlue.r][nBlue.c]) continue;

                    visit[nRed.r][nRed.c][nBlue.r][nBlue.c] = true;

                    // Queue에 추가
                    q.add(new Turn(nRed.r, nRed.c, nBlue.r, nBlue.c));
                }
            }

            // 10번 이하로 성공할 수 없다면
            if(++time > 10) return 0;
        }
        return 0;
    }

자료구조

pair

Pair 클래스 생성

//pair 클래스 생성
public Pair(){
	private int x; //은닉화 
	private int y;
    //생성자
    Pair(int x, int y){
    	this.x = x;
        this.y = y;
    }
}

queue 생성 및 추가, 추출

//queue 선언
Queue<Pair> q = LinkedList<>();

//queue 추가
q.add(new Pair(x,y));

//queue 추출
int first = q.peek().x;
int second = q.peek().y;

//queue 삽입
Pair temp = new Pair(10,20); //초기값 셋팅
temp.x = 20; //변경
q.add(temp); //queue에 삽입

형변환

기타