23297번 - 전파와 병합 1

주헌이는 최근에 엑셀을 열심히 공부하고 있다. 엑셀의 아름다운 작동 방식에 감동 받은 주헌이는 본인이 직접 엑셀과 같은 '스프레드 시트'를 개발하기로 마음 먹게 된다. 주헌이가 직접 개발했기 때문에 실제 작동방식은 엑셀과 조금 다른 부분이 있다.

스프레드 시트에서 직사각형 격자 한 칸을 '셀'이라고 부른다. 각 셀은 자신의 위치를 좌표로 나타낼 수 있다. 이때 열(row) 성분은 알파벳 대문자로 나타내며 행(column) 성분은 1이상의 정수로 나타낸다. 열 성분은 A부터 시작하여 한 칸씩 커질수록 B, C, D...Z 와 같은 알파벳 순서를 따른다. 또한 Z 다음에는 AA이며 그 이후에는 AB, AC...AZ, BA, BB, BC, ... BZ, CA, CB, ... ZZ 와 같이 알파벳 대문자 26개로 이루어진 26진법 규칙을 따른다.

이 스프레드 시트에서는 셀을 변수로 취급해서 수식을 작성할 수 있는데 이것을 우리는 셀을 '참조'한다고 얘기한다. 그리고 셀을 참조하는 과정에서 cycle이 발생하는 현상을 순환 참조라고 부른다. 순환 참조는 참조하는 대상이 서로 물려있어서 참조할 수 없는 상태를 말한다. 순환 참조는 데이터의 큰 문제를 야기할 수 있으므로 순환 참조를 이루고 있는 셀들을 유효하지 않은 셀 이라고 부른다.

또한 '유효하지 않은 셀'은 자신을 참조하고 있는 다른 셀들에게도 전파된다. 즉 직접적으로 '유효하지 않은 셀'이 아니어도, 그 셀이 참조하고 있는 셀 중에서 하나라도 '유효하지 않은 셀'이 존재한다면 그 셀 또한 '유효하지 않는 셀'로 변하며 이 과정을 통해 변한 셀을 전파된 셀이라고 부른다. 이러한 전파 과정은 연쇄적으로 일어나기 때문에 전파된 셀을 참조하는 셀 역시 전파된 셀로 변하게 된다. 위 과정이 모두 일어난 뒤에도 '유효하지 않은 셀'로 변하지 않은 셀들은 유효한 셀이라고 부른다. 유효한 셀이 되기 위해선 자신이 참조하는 셀 중에서 유효하지 않은 셀이 있어서는 안된다.

아래 <그림 1>에서 [A1,B1,A2]은 cycle을 이루고 있기 때문에 '순환 참조'를 이루고 있는 상태이고, A1,B1,A2는 '유효하지 않은 셀'이다. 그리고 A3은 처음에는 '유효한 셀'이었지만, 자신이 참조하고 있는 A2가 '유효하지 않은 셀'의 상태가 전파되어 A3도 '전파된 셀'로 변하였다. 또한 B3 역시 전파된 셀인 A3을 참조하였기 때문에 자신도 전파된 셀로 변하게 된다.   

<그림 1>

위 과정이 모두 일어난 뒤에, 여기서 셀 병합이라는 신기한 기능이 하나가 추가된다. 셀 병합은 다음과 같은 조건을 만족할 때 일어난다.

1.  셀 병합이 일어나기 위해선 '순환 참조'를 이루는 셀들의 구성 상태가 '완전한 직사각형' 형태이어야 한다. '완전한 직사각형' 형태란 연속적으로 이어진 가로와 세로의 직사각형을 선택했을 때, 내부에 존재하는 모든 셀들이 하나의 순환 참조를 이룰 때를 말한다.
2.  셀 병합이 일어나기 위해선 반드시 순환참조를 이루고 있는 모든 셀들이 참여해야 한다.
3.  위 1, 2번 조건을 모두 만족할 경우, 셀 병합은 자동적으로 일어난다.
4.  셀 병합이 완료된 후, 병합된 셀은 한 칸으로 합쳐지며 그 칸의 좌표는 병합을 이루었던 가장 왼쪽 위 셀의 좌표로 변한다.

셀 병합이 완료된 이후, 직사각형을 이루었던 모든 셀이 '유효하지 않은 셀'을 참조하지 않는다면 병합된 셀은 유효한 셀로 변한다. 다시 말해 직사각형을 이룬 셀들 중 하나라도 '유효하지 않은 셀'을 참조한다면 병합된 셀은 여전히 유효하지 않은 상태이다. 병합으로 인한 '유효한 셀'로 변하는 과정 역시 연쇄적으로 일어난다. 단, '순환 참조'를 직접적으로 이루고 있는 셀에게는 전파되지 않는다.    

아래 <그림 2>에서 [A1, B1, A2, B2]은 처음에는 '순환 참조'를 이루고 있고, A3은 A2를 참조하고 있기 때문에 전파된 셀이었다. 하지만 [A1, B1, A2, B2]가 '셀 병합'이 일어나 하나의 셀 [A1]이 된다. 또한 병합되기 이전에 [A1, B1, A2, B2] 중에서 유효하지 않은 셀을 참조하는 셀이 없었으므로 유효한 셀로 변하며, 이를 참조하고 있던 A3도 '유효한 셀'로 변한고 연쇄적으로 B3도 '유효한 셀'로 변한다.

<그림 2>

열의 크기가 R, 행의 크기가 C 인 스프레드 시트에서 각 셀이 참조하고 있는 셀의 정보가 주어질 때, 유효한 셀의 좌표를 사전 순으로 모두 출력하여라.

이 문제에서 자기 자신을 참조하는 셀은 없으며, 각 셀은 최대 2개의 서로 다른 셀을 참조할 수 있다고 가정한다.

첫째 줄에 열과 행의 크기 R, C 가 각각 주어진다.(1 ≤ R ≤ 999 , 1 ≤ C ≤ 702)

둘째 줄부터 스프레드 시트의 각 칸이 참조하는 셀의 좌표가 주어진다. 알파벳 대문자는 A부터 첫 번째 행을 나타내고, 정수는 1부터 첫 번째 열을 나타낸다.

셀의 좌표는 알파벳 대문자 한글자 또는 두글자와 1이상 999이하의 정수가 결합된 형태이다. 다시 말해 가장 왼쪽 위 셀의 좌표는 A1, 가장 왼쪽 아래 셀의 좌표는 A999,가장 오른쪽 위 셀의 좌표는 ZZ1, 가장 오른쪽 아래 셀의 좌표는 ZZ999이다. (문제 하단 Note의 <그림 9> 참고)

만약 두 개의 셀을 참조한다면 +로 구분해서 주어진다. 아무 셀도 참조하지 않는다면 . 으로 주어진다.

입력으로 주어진 셀의 범위보다 큰 좌표는 입력으로 주어지지 않는다.

첫째 줄에 유효한 셀의 개수를 출력한다.

다음 줄에는 유효한 셀의 좌표를 사전 순으로 모두 출력하여라. 사전 순에 대한 자세한 설명은 문제 하단 '노트'에 설명되어 있다.

<그림 8>

1. <그림 8>는 셀 병합의 잘못된 예시이다. 셀 병합을 이루기 위해서는 완전한 직사각형 형태이어야 한다.

<그림 9>

2. <그림 9>은 R = 99, C = 702 일 때 스프레드 시트의 셀의 좌표를 나타낸 것이다.

3. 이 문제에서 정의하는 사전 순의 원칙은 다음과 같다.

• 알파벳 대문자는 A가 가장 앞에 오며, 그 이후로 B,C,D...Z와 같이 알파벳 순서를 따른다. 예를 들어 A999 는 B1 보다 앞에 와야 한다.
• 숫자는 0이 가장 앞에 오며, 그 이후로 1,2,...9와 같이 오름차순을 따른다. 예를 들어 A11 은 A2 보다 앞에 와야 한다.
• 임의의 두 문자열에서 같은 자릿수에 하나는 알파벳, 다른 하나는 숫자가 있다면, 숫자가 있는 문자열이 앞에 와야한다. 예를 들어 A11 은 AA1 보다 앞에 와야 한다.
• 임의의 두 문자열에서 하나의 문자열이 다른 하나의 문자열의 부분 문자열이라면, 길이가 짧은 부분 문자열이 앞에 와야한다. 예를 들어 A1 은 A11 보다 앞에 와야 한다.

위 규칙을 모두 적용하여 [ A11, AA1, A2, A1, B1 ] 의 문자열을 사전 순으로 정렬한 결과는 [ A1, A11, A2, AA1, B1 ]이다.