공부흔적

문제 링크

풀이 ) DFS

1. 각 역이 순환선에 포함된 역인지 확인
2. 사이클에서 지선이 있는 역에서부터 각 지선 노선의 거리 구하기

위의 순서대로 DFS만을 이용해서 구했다.

  먼저 각 역이 순환선인지 확인하기 위해 모든 점에 대해서 현재 점으로 되돌아 오는지 확인했다. (checkCycle()) 이때 순환선을 확인하면 순환선 내의 역은 한번에 구해 반복 횟수를 줄일 수 있다. (return type이 boolean인 이유)

  순환역에 속한 역 중 차수가 3 이상인 역은 지선으로 갈 수 있는 역이므로 이 역을 시작으로해서 지선에 포함된 역까지의 거리를 구한다. (getDistance())

코드 )

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

class Main {

    static int n;
    static List<Integer>[] adj;
    static boolean[] visited;
    static boolean[] isCycle;
    static int[] distance;

    public static void main(String[] args) throws IOException {
        input();
        checkCycle();	// 사이클 확인
        getDistance();	// 거리 구하기
    }

    static void getDistance() {
        distance = new int[n+1];
        visited = new boolean[n+1];

		// 사이클에서 벗어나는 길 거리 구하기
        for(int i = 1; i <= n; ++i)
            if(isCycle[i] && adj[i].size() > 2)
                searchRoute(i);

		// 거리 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= n; ++i) {
            sb.append(distance[i] + " ");
        }
        System.out.println(sb.toString());
    }

    static void searchRoute(int i) {
        for(int next: adj[i]) {
            if(isCycle[next] || distance[next] > 0) {
               continue;
            }
            distance[next] = distance[i]+1;
            searchRoute(next);
        }
    }

    static void checkCycle() {
        isCycle = new boolean[n+1];

        for(int i = 1; i <= n; ++i)
            if(!isCycle[i]) {
                visited = new boolean[n+1];
                dfs(i, i, 0);
            }
    }

    static boolean dfs(int strt, int i, int cnt) {
        for(int next: adj[i]) {
            if(next == strt) {
            // 바로 돌아오는 경우를 cnt를 사용해서 방지
                if (cnt > 1)
                    return isCycle[i] = true;
                else
                    continue;
            }
            
            // 다음이 사이클(사이클이 아닌 곳에서 사이클로 -> 사이클 아님)
            // 현재가 사이클(조건 만족)
            // 이미 방문(사이클인지 여부가 이미 나옴)
            if(isCycle[next] || isCycle[i] || visited[next])
                continue;
            visited[next] = true;
            isCycle[i] = dfs(strt, next, cnt+1);
        }
        return isCycle[i];
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        adj = new List[n+1];
        for(int i = 1; i <= n; ++i)
            adj[i] = new ArrayList<>();
        for(int i = 0; i < n; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            // 양방향
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            adj[v1].add(v2);
            adj[v2].add(v1);
        }
    }
}

알게된 점 )

  그래프에서 정점과 간선의 개수가 같고 모두 이어져 있으면 사이클은 단 하나만 가능하다.

문제 링크

풀이 ) DFS

  적록색약이 아닌 사람은 R, G, B를 각각 따로 / 적록색약인 사람은 R과G를 구분하지 않고, B만 따로 봐주면 된다.

  각각 다르게 DFS를 구현할 수 있지만 같은 메서드에 대해서 flag를 다르게 넘겨주어 다음 칸이 유효한지 확인하는 부분만 다르게 구현했다.

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

public class Main {
    static int n;
    static char[][] board;
    static boolean[][] visited;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());
        board = new char[n][];
        for(int i = 0; i < n; ++i)
            board[i] = br.readLine().toCharArray();

        visited = new boolean[n][n];
        int ans = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(!visited[i][j]){
                    dfs(i, j, board[i][j], false);
                    ans++;
                }
            }
        }
        sb.append(ans).append(' ');

        visited = new boolean[n][n];
        ans = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(!visited[i][j]){
                    dfs(i, j, board[i][j], true);
                    ans++;
                }
            }
        }
        sb.append(ans);
        System.out.println(sb);
    }

    static void dfs(int x, int y, char c, boolean flag){
        visited[x][y] = true;
        for(int dir = 0; dir < 4; ++dir){
            int nx = x+dx[dir], ny = y+dy[dir];
            if(!isIn(nx, ny, c, flag) || visited[nx][ny])
                continue;
            dfs(nx, ny, c, flag);
        }
    }

    static boolean isIn(int x, int y, char c, boolean flag){
        if(flag){
            if(c == 'B')
                return 0 <= x && x < n && 0 <= y && y < n && board[x][y] == 'B';
            else
                return 0 <= x && x < n && 0 <= y && y < n && board[x][y] != 'B';
        }
        return 0 <= x && x < n && 0 <= y && y < n && board[x][y] == c;
    }
}

주의 )

- visited와 ans의 초기화

문제 링크

풀이 )

• puyo( ): 터지는지 여부
• dfs( ): puyo( )에서 연속된 4개의 블록이 있는지 확인하기 위한 재귀함수
• pung( ): 4개 이상의 블록이 붙어있는 경우 같은 종류의 블록을 모두 터뜨림
• fall( ): 블록 아래로 내리기

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> field(12);
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void fall(){
    for(int c = 0; c < 6; ++c){
        for(int r = 11; r > 0; --r){
            while(field[r][c] == '.'){
                int flag = true;
                for(int i = r; i > 0; --i){
                    if(field[i][c] != '.')
                        flag = false;
                    field[i][c] = field[i-1][c];
                }
                if(flag){
                    if(field[0][c] == '.')
                        break;
                }
                field[0][c] = '.';
            }
        }
    }
}

void pung(int x, int y, char c){
    field[x][y] ='.';
    for(int dir = 0; dir < 4; ++dir){
        int nx = x+dx[dir];
        int ny = y+dy[dir];
        if(nx < 0 || nx >= 12 || ny < 0 || ny >= 6)
            continue;
        if(field[nx][ny] == c)
            pung(nx, ny, c);
    }
    return;
}

int dfs(int x, int y, char c, vector<vector<bool> > visited){
    int ret = 1;
    visited[x][y] = true;
    for(int dir = 0; dir < 4; ++dir){
        int nx = x+dx[dir];
        int ny = y+dy[dir];
        if(nx < 0 || nx >= 12 || ny < 0 || ny >= 6 || visited[nx][ny])
            continue;
        if(field[nx][ny] == c)
            ret += dfs(nx, ny, c, visited);
        if(ret >= 4)
            break;
    }
    return ret;
}

bool puyo(){
    bool ret = false;
    vector<vector<bool> > visited(12, vector<bool>(6));
    for(int r = 0; r < 12; ++r){
        for(int c = 0; c < 6; ++c){
            if(field[r][c] == '.' || visited[r][c])
                continue;
            if(dfs(r, c, field[r][c], visited) < 4)
                continue;
            pung(r, c, field[r][c]);
            ret = true;
        }
    }
    return ret;
}

int main(void){
    for(int i = 0; i < 12; ++i)
        cin >> field[i];

    int ans = 0;
    while(1){
        if(!puyo()){
            cout << ans << '\n';
            return 0;
        }
        ans++;
        fall();
    }
}

주의)

• puyo( )에서 dfs( )의 결과가 4가 넘어가면 바로 재귀함수를 호출할 필요없이 터뜨리기 때문에 바로 continue 처리해준다.(안해주면 시간초과)
• 터뜨릴때는 한번에
• 떨어뜨리는 부분에서 실수가 많이 일어나는 편이다.

문제 링크

풀이 )

  여태까지 풀었던 dfs에서와 달리 방문한 칸을 저장하는 배열 대신, 사용한 알파벳을 저장하는 배열을 사용했다.

  처음 (0, 0)을 시작으로 방문한 칸의 알파벳의 사용 여부를 갱신하고, 4방향에 대해서 탐색한 최댓값+1(현재칸)을 반환한다.

  각 방향에 대해 영향을 주지 않기 위해 다음 방향을 가기 전에 다음 칸 알파벳의 사용 여부를 초기화해준다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

int r, c;
vector<string> board;
bool used[26];

int dfs(int x, int y){
    int ret = 0;
    used[board[x][y]-'A'] = true;
    for(int dir = 0; dir < 4; ++dir){
        int xx = x+dx[dir];
        int yy = y+dy[dir];
        if(xx < 0 || xx >= r || yy < 0 || yy >= c)
            continue;
        if(used[board[xx][yy]-'A'])
            continue;
        ret = max(ret, dfs(xx, yy));
        used[board[xx][yy]-'A'] = false;
    }
    return ret+1;
}

int main(void){
    cin >> r >> c;
    for(int i = 0; i < r; ++i){
        string s;
        cin >> s;
        board.push_back(s);
    }

    int ans = dfs(0, 0);

    cout << ans;
}

문제 링크

풀이 )

  처음 모눈종이의 모든 칸이 false이므로 , 주어지는 직사각형이 덮는 영역을 true로 고쳐준 후

(0, 0)을 시작으로 덮지 않은, 즉 칸이 false이고, 방문여부 또한 false인 칸을 찾아

DFS를 사용하여 영역의 넓이를 구해 vector에 넣어준다.

  마지막 칸까지 확인한 후 vector에 들어가있는 영역의 넓이를 정렬해준 뒤 출력한다.

* 문제에서는 좌하단을 (0, 0)으로 잡았기 때문에 내가 생각한 그림과 상하반전이 되어있지만, 결괏값에 영향을 주지 않는다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, k, area;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool arr[100][100];
bool visited[100][100];
vector<int> vc;

void dfs(int x, int y){
    visited[x][y] = true;
    area++;
    for(int dir = 0; dir < 4; ++dir){
        int xx = x+dx[dir];
        int yy = y+dy[dir];
        if(xx < 0 || xx >= n || yy < 0 || yy >= m)
            continue;
        if(arr[xx][yy] || visited[xx][yy])
            continue;
        dfs(xx, yy);
    }
    return;
}

int main(void){
    cin >> n >> m >> k;
    int cnt = 0;
    while(k--){
        int lx, ly, rx, ry;
        cin >> ly >> lx >> ry >> rx;
        for(int x = lx; x < rx; ++x){
            for(int y = ly; y < ry; ++y){
                arr[x][y] = true;
            }
        }
    }

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(!arr[i][j] && !visited[i][j]){
                cnt++;
                area = 0;
                dfs(i, j);
                vc.push_back(area);
            }
        }
    }

    sort(vc.begin(), vc.end());
    cout << cnt << endl << vc.front();
    for(vector<int>::iterator it = vc.begin()+1; it != vc.end(); ++it)
        cout << ' ' << *it;
    cout << endl;
}

주의 )

- 문제에서 주어지는 입력순서 m, n, k는 세로, 가로 이지만 이후 k줄에 대해서는 x, y 순서로 주어진다.

문제 링크

풀이 )

  좌측 상단의 좌표를 (0, 0)이라 하고, 파이프의 방향을 가로는 0, 대각선은 1, 세로는 2라 하면,

  시작 좌표는 (1, 0)이고 방향은 0이라고 할 수 있다.

  매번 함수가 호출될 때 현재 방향에 따라 다음에 둘 수 있는 방향은 다음과 같다.

• 가로 -> 가로 | 대각
• 대각 -> 가로 | 대각 | 세로
• 세로 -> 대각 | 세로 

  따라서 각 상황에 맞게 좌표를 수정해주고, 다음 호출 시

• 좌표가 범위를 벗어나는 경우(x >= n || y >= n)
• 벽으로 가로 막혀있는 경우(home[y][x] == 1)
• 대각선으로 이동할 때(dir == 1) 위나 왼쪽이 벽으로 막혀있는 경우( (y>0 && home[y-1][x]) || (x>0 && home[y][x-1]) )

  위의 3가지의 경우 함수를 종료 시켜주고,

  마지막인 x, y좌표가 각각 n-1인 경우 가짓수를 하나 늘려준다.

#include <cstdio>

int dx[3] = {1, 1, 0};
int dy[3] = {0, 1, 1};
int n, ans, home[17][17] = {0, };

void dfs(int x, int y, int dir);

int main(void)
{
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
      scanf("%d", home[i]+j);

  dfs(1, 0, 0);
  printf("%d\n", ans);
}

void dfs(int x, int y, int dir)
{
  if(x >= n || y >= n)
    return;
  if(home[y][x])
    return;
  if(dir == 1){
    if((y>0 && home[y-1][x]) || (x>0 && home[y][x-1]))
      return;
  }
  if(x == n-1 && y == n-1){
    ++ans;
    return;
  }

  if(dir == 0){
    dfs(x+dx[0], y+dy[0], 0);
    dfs(x+dx[1], y+dy[1], 1);
  }
  else if(dir == 1){
    dfs(x+dx[0], y+dy[0], 0);
    dfs(x+dx[1], y+dy[1], 1);
    dfs(x+dx[2], y+dy[2], 2);
  }
  else{
    dfs(x+dx[1], y+dy[1], 1);
    dfs(x+dx[2], y+dy[2], 2);
  }
}

주의점 )

  함수를 종료시키는 경우를 답을 증가시키는 경우보다 위에 두어야 답이 아닌데 세는지 않을 수 있다.

  ex ) dfs( )의 4번째 if 블록을 3번째 if 블록과 위치를 바꾸게 된다면

  4

  0 0 0 0

  0 0 0 0

  0 0 0 1

  0 0 1 0

  과 같은 입력에 대해서 오답을 출력하게 된다.