춤추는 개발자

문제 출처 https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경 www.acmicpc.net 접근 방식 및 풀이 - BFS를 활용한다. - 명령어를 한번씩 실행하면서 결과값을 저장하고, 계속 돌다가 출력해야하는 값이 나..

문제 출처 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 접근 방식 및 풀이 - BFS와 Deque 개념 활용한 문제 - 핵심 알고리즘은 BFS에서 0이면 그냥 가고, 1이면 부수고 가야하므로 dist 배열에 1을 더해주는 것이다. - 프로그래밍에서 배열과 수학에서의 x, y 좌표.. 가 헷갈려서 중간에 런타임에러 엄청 걸렸다. 소스 코드 1 2 3 4 5 6 7 8 9 ..

문제 출처 https://www.acmicpc.net/problem/1963 0){// T가 양수일때 진행 StringTokenizer st = new StringTokenizer(br.readLine()); int A = Integer.parseInt(st.nextToken()); int B = Integer.parseInt(st.nextToken()); if(A==B){ System.out.println(0); continue; } int ret = bfs(A,B); System.out.println(ret); } } private static int bfs(int A, int B){ discovered = new boolean[10000]; Queue queue = new LinkedList(); ..

문제 출처 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 접근 방식 및 풀이 - BFS 이용 - 아래 블로그 참고함. https://qlyh8.tistory.com/157 백준 2178번: 미로 탐색 문제 출처: https://www.acmicpc.net/problem/2178 참고 BFS(Breadth-First Search): http://qlyh8.tistory.com/30?category=731166 BFS 문제: http://qlyh8.tistory.com/31?c..

문제 출처 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북 www.acmicpc.net 접근 방식 및 풀이 - 키워드는 간척사업을 통해 다리를 만들수 있는 최소거리, BFS 활용이다. - 너무 어려워서 아래 블..

문제 출처 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 www.acmicpc.net 접근 방식 및 풀이 - BFS, DFS 모두 사용하여 해결할 수 있다. - 아래 블로그 내용을 참고하여 구현하였다. (개인적으로..

문제 출처 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 접근 방식 및 풀이 아직도 감이 안온다.. 이해한 부분까지는 코드에 주석으로 달았다. 참고 사이트 : https://ballpython.tistory.c..

문제 출처 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마 www.acmicpc.net 접근 방식 및 풀이 BFS활용.. 너무너무 어렵다.!ㅜ 직접 그려가면서 이해했습니다. # BFS 구현 과정 소스 코드 impor..