hoding hoding

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 주요 로직은 다음과 같다. 1. 방문해야할 노드를 큐에 넣어준다. 2. 큐에 있는 원소들을 하나씩 poll한 뒤 방문처리를 위한 bool배열을 초기화 해준다.(poll한뒤 큐에 원소가 없는 경우는 모든 노드를 방문했으므로 "YES"를 출력하고 return) 3. poll한 노드와 인접하면서 방문하지 않은 노드에 대해서 하나의 큐를 더 만들어 bfs 탐색을 한다. 4. 인접한 노드와 방문해야할 큐의..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 거리를 구하는 알고리즘으로는 다익스트라, 플로이드 와샬이 있는데 해당 문제는 모든 원소에 대해서 최소비용을 구해야하기 때문에 플로이드 와샬 알고리즘으로 풀이하였습니다. 플로이드 와샬 알고리즘이란 a,b,c의 세개의 정점이 있다고 가정했을 때 b에서 c로 가는 비용과 b에서 a, a에서 c로 경유해서 가는 비용 중 최소값을 구할 수 있는 알고리즘으로 삼중 for문을 사용해 구현할 수 있습니다. 해당..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 문제를 보고 처음 시도한 접근은 양분, 나무들의 나이를 기준으로 정렬된 우선순위 큐가 필드값으로 있는 map이란 클래스와 map을 저장할 2차원 배열을 만든 뒤 나무가 있는 좌표가 저장된 set을 만들어 해당 문제를 풀어보았습니다. 클래스 객체를 set에 저장하기 위해서 클래스에서 좌표값을 기준으로 hashcode함수와 equals 함수를 재정의하여 구현하였으나 시간초과가 났고 잘..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 : 핵심 로직은 다음과 같습니다. 1. 일반적인 2차원 배열로는 층수를 표현할 수 없기에 3차원 배열로 각층에 대한 정보를 입력받는다. 2. bfs 함수 내에서는 몇번째에 탈출했는 지 알기위해서 무한루프로 반복문을 진행하며 그 안에서 큐의 사이즈만큼 반복한다. 3. 미리 정의해둔 dh, dx, dy 배열 정보를 활용하여 지나갈 수 있는 곳이거나, 방문하지 않은 좌표값이라면 큐에 넣어주고 함수가 종..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net bfs로 풀 수 있는 문제이다. 도화지를 입력 받은 뒤 원소의 값이 1이거나, 아직 방문하지 않은 곳이라면 하나의 그림이기 때문에 cnt 변수에 1을 더해준다. 그리고 bfs함수를 실행시켜 상,하,좌,우에 인접한 1의 개수만큼 큐에 추가하며 탐색을 진행해준 뒤 max의 값을 업데이트 해주어 문제에서 제시한 값을 도출할 수 있었다. import java.io.BufferedReader; import ja..

https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 풀이 : 1. 우선 왼쪽에 서있는 사람들의 수를 저장할 배열을 생성해주고 입력 값으로 받아준다. 2. 비교하기 위해 Integer.MAX_VALUE값이 저장된 배열을 하나 더 생성해준다. 3. 첫번째 사람부터 for문을 돌며 최대값이 저장되어 있는 order 배열의 값과 현재 인덱스인 i를 비교하며 값이 크다면 tmp 변수에 1을 더해주고 index의 값은 크든 적든 1을 더해주며 순환해준..

https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 풀이: 1. 스위치의 상태를 입력받는다. 2. 학생의 성별, 숫자를 담을 클래스와 학생 배열을 생성하고 입력받는다. 3. 학생의 성별이 남자라면 for문을 통하여 배수의 값을 업데이트 해주고 여자일 경우에는 좌우로 대칭한 값을 업데이트 해준다. 문제에서 제시한 조건만 잘 지켜주면 막히는 부분없이 풀 수 있는 문제였던 거 같습니다. 라고 생각했는데 출력형식이 계속 잘못됐다고 해서 확인하니 출력..

https://www.acmicpc.net/problem/20125 20125번: 쿠키의 신체 측정 쿠키런은 데브시스터즈에서 제작한 모바일 러닝 액션 게임이다. 마녀의 오븐에서 탈출한 쿠키들과 함께 모험을 떠나는 게임으로, 점프와 슬라이드 2가지 버튼만으로 손쉽게 플레이할 수 있는 www.acmicpc.net 풀이 : 1. 쿠키의 머리를 찾은 뒤 머리의 바로 한칸 아래가 심장이므로 hX, hY 변수에 심장에 위치를 업데이트한다. 2. 쿠키의 왼팔, 오른팔, 허리 순으로 dfs 탐색을 진행하여 길이를 구해준다. 허리의 경우에 허리의 끝 양쪽에 다리가 있으므로 해당 좌표를 static 변수에 업데이트 해준다. 3. bX, bY 변수는 허리의 끝 지점이다. 양쪽 다리에 대해서 dfs 탐색을 진행하여 양다리의 ..