백준 1058번 친구(Java)

1058번: 친구 (acmicpc.net)

1058번: 친구

 

<어려웠던 부분>

1. 여러 줄의 문자열을 Scanner로 입력 받아 split 해서 문자 하나씩 배열에 저장하는 부분

		int n, i, j;
		String tmp;
		String [] arr=new String[50];
		String [][] f=new String [50][50];
		String [][] r=new String [50][50];
		
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		sc.nextLine();
		for(i=0; i<n; i++) {
			tmp=sc.nextLine(); // nextLine()으로 문자열 한 줄을 입력 받고
			arr=tmp.split(""); // ✨arr이라는 배열에 split한 문자 하나하나를 각각 저장
			for(j=0; j<n; j++) {
				f[i][j]=arr[j]; // arr 배열에 담긴 문자 하나하나를 f라는 2차원 배열에 재저장
				r[i][j]=arr[j];
			}
		}

문제에서 제시하는 출력에 맞게 프로그램은 다 짰는데,

split 해서 입력 받는 부분에서 자꾸 문제가 생겨 출력을 확인할 수 없었고 문제를 계속해서 풀지 못했다.

그래서 과거의 내 코드를 리뷰하면서 비슷하게 문자열을 입력받는 부분 코드를 확인할 수 있었고,

위와 같이 수정했다.

 

문제점이 무엇이었냐 하면, split을 바로 f[i][j]라는 이차원 배열에 적용하려고 했던 것이었다.

        n=sc.nextInt();
		sc.nextLine();
		for(i=0; i<n; i++) { //행
			tmp=sc.nextLine();
			for(j=0; j<n; j++) { //열
				f[i][j]=tmp.split(""); ⛔ 오류 코드
			}
		}

tmp를 통해서 문자를 입력 받고, tmp.split을 하면

이중 for문 내에서 바로 split으로 값이 배열에 하나씩 저장될 것이라 생각했는데

split은 위의 오류 코드에서처럼 반복(for문)을 통해 하나씩 저장이 수행되는 것이 아니라,

split이라는 함수 자체가 하나씩 나누어 저장을 수행하는 것이기 때문에 문제가 생겼던 것이다.

따라서 (임시로 설정한) arr이라는 1차원 배열에 tmp.split의 결과값을 저장하고,

f라는 2차원 배열에는 다시 값을 따로 지정해주어야하는 것이다.

 

cf. 하지만, 사실 아직까지도 아래와 같은 코드와 arr 배열을 사용하지 않은 코드의 차이점이 무엇인지는 잘 모르겠다.

			for(i=0; i<n; i++) {
			tmp=sc.nextLine();
			f[i]=tmp.split("");
			r[i]=tmp.split("");
			}

 

2. nextInt() 이후 nextLine() 입력으로 바꾸기

이건 계속해서 겪어온 문제였는데, nextInt()만 계속 사용하다보니 잊고 있었다.

nextInt()를 통해 입력 받은 후, nextLine() 로 입력을 받으려는 경우

중간에 Enter 값이 들어가 뒤에 입력받는 과정이 제대로 이루어지지 않을 수 있다.

따라서 그 둘 사이 sc.nextLine()을 넣어 중간 Enter 입력을 처리해주어야 한다.

잊지 말자!

		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		sc.nextLine(); // ✨nextInt()와 nextLine() 사이 생기는 Enter 값의 입력 처리해주기
		for(i=0; i<n; i++) {
			tmp=sc.nextLine();
			arr=tmp.split("");
			for(j=0; j<n; j++) {
				f[i][j]=arr[j];
				r[i][j]=arr[j];
			}
		}

 

3. 출력값 오류

위에서는 Run 이전에 생기는 문제였다면, 위의 두 가지 문제를 해결한 이후 생긴 출력값 오류에 대해 이야기해보려 한다.

우선, 백준에서 제시된 5가지의 예제 중 4개에서는 제대로 출력값이 나왔으나,

4번째 예제에서 오류가 발생하였다.

 

이 과정을 해결하는 데에도 꽤나 오랜 시간이 걸렸는데

많은 고민 끝에 도출한 문제점은

예를 들어, A와 B가 친구이고, C와 B가 친구이기에 A와 C를 2-친구라고 볼 수 있을 때,

그렇다면 C와 D가 친구라면, A와 D도 친구로 볼 수 있는가 라는 것이다.

앞의 과정이 선행된다면 A와 C가 2-친구가 되고, C와 D가 친구이기에  A와 D도 2-친구가 되겠지만

사실상 이는 문제에서 말한 2-친구 조건에 해당하지 않는다.

정확히는 "2-친구의" 2-친구가 되는 것이다.

이렇게 되면 예제 4와 같이 모두가 친구가 되는 오류가 발생할 수 있다.

따라서 이전에 선행된 for문으로 2-친구(즉, "Y")로 "변한" 관계의 경우는

다음 진행될 for문에 영향을 주지 않도록 바꾸어주어야 한다.

 

그래서 나는 f 배열 외에 r 배열을 추가로 선언하여

f 배열에는 입력된 값만을,

r 배열에는 입력된 값+변경된 값을 저장하여 문제를 다시 풀었다.

 

import java.util.Scanner;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n, i, j;
		String tmp;
		String [] arr=new String[50];
		String [][] f=new String [50][50];
		String [][] r=new String [50][50];
		
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		sc.nextLine();
		for(i=0; i<n; i++) { //행
			tmp=sc.nextLine();
			arr=tmp.split("");
			for(j=0; j<n; j++) { //열
				f[i][j]=arr[j];
				r[i][j]=arr[j];
			}

		}
		
		for(j=0; j<n; j++) { //열 (A와 친구 여부)
			for(i=0; i<n; i++) { //행 (A,B,C,...)
				for(int k=i+1; k<n; k++) {
					if((f[i][j].equals("Y"))&&(f[k][j].equals("Y"))) {
						r[i][k]="Y";
						r[k][i]="Y";
					}
					
				}
			}
		}
		
		int max=0;
		for(i=0; i<n; i++) { //행
			int count=0;
			for(j=0; j<n; j++) { //열
				if (r[i][j].equals("Y")) count++;
			}
			if (max<count) max=count;
		}
		
		System.out.println(max);
	}
}

 

결과적으로, 성공!