뚱땅뚱땅

www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 1. BFS public class BOJ_11725 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int N = Integer.parseInt(in.readLine()); // 인접리스트 만들기 A..

www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 풀이 BFS 문제다. 큐에다가 이동거리를 확인할 수 있도록 좌표와 이동거리가 포함된 배열을 넣도록 했다. 처음에 visited 처리를 아래 주석의 위치에다가 했다가 메모리 초과가 나서 큐에 삽입하는 시점으로 바꿨더니 문제가 풀렸다. 여기서 주의해야 할 케이스는 시작점과 목표점이 동일할 때이다. 답을 0으로 먼저 처리 안하고 저 방식대..

www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 내 풀이 bfs 함수에서 for문으로 4방 탐색 안하고 while 문에서 x,y를 업데이트하는 식으로 했는데 틀렸다! for 문으로 4방 탐색하는게 안전한 듯 하다. public class BOJ_3184 { static int[] dx = { 0, 1, 0, -1 }; static int[] dy = { 1, 0, -1, 0 }; static int R, C; static char[][] matr..

www.acmicpc.net/problem/16935 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 풀이 배열 돌리기 1과 4를 했다면 쉽게 풀 수 있다. 여기서 오른쪽, 왼쪽 방향으로 회전할 때 행렬의 크기가 반대로 변경되니까 이점만 유의하면 된다. public class BOJ_16935 { static int N; static int M; static int[][] matrix; public static void main(Str..

www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 시계방향 회전의 원리만 알면, 이후에는 순열로써 문제를 풀면 된다. N*M 행렬이라고 할 때, min(N,M) / 2가 회전해야할 둘레의 개수라고 볼 수 있다. (위의 그림 참고) 그리고 처음 회전의 시작점을 (0,0)이라고 하고, 회전횟수가 i 번째라고 할 때, 이 i번째 둘레를 회전할 때의 시작점은 (i,i) 다. 이를 이용해서 둘레 회전을 시켜주면 된다! 방향이 너무 헷..