전파와 병합 1

주헌이는 최근 엑셀을 열심히 공부하고 있다. 엑셀의 작동 방식에 감동한 주헌이는 직접 엑셀과 같은 '스프레드 시트'를 개발하기로 했다. 직접 개발한 프로그램이므로 실제 작동 방식은 엑셀과 조금 다른 부분이 있다.

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

이 스프레드 시트에서는 셀을 변수처럼 다루어 수식을 작성할 수 있다. 이를 셀을 '참조'한다고 한다. 셀을 참조하는 과정에서 순환이 생기는 현상을 순환 참조라고 부른다. 순환 참조는 참조 대상이 서로 얽혀 있어서 어느 셀도 참조할 수 없는 상태를 말한다. 순환 참조는 데이터에 큰 문제를 일으킬 수 있으므로, 순환 참조를 이루는 셀들을 유효하지 않은 셀이라고 부른다.

'유효하지 않은 셀'은 이를 참조하는 다른 셀에도 전파된다. 직접 순환 참조에 속하지 않은 셀이라도 참조하는 셀 중 하나라도 유효하지 않은 셀이면, 그 셀도 유효하지 않은 셀이 된다. 이렇게 바뀐 셀을 전파된 셀이라고 부른다. 전파는 연쇄적으로 일어나므로, 전파된 셀을 참조하는 셀도 전파된 셀이 된다. 전파 과정이 모두 끝난 뒤에도 유효하지 않은 셀로 바뀌지 않은 셀을 유효한 셀이라고 부른다. 유효한 셀이 되려면 자신이 참조하는 셀 중에 유효하지 않은 셀이 없어야 한다.

<그림 1>

<그림 1>에서 [A1, B1, A2]는 순환을 이루고 있어 순환 참조 상태이며, A1, B1, A2는 유효하지 않은 셀이다. A3은 처음에는 유효한 셀이었지만, 유효하지 않은 A2의 상태가 전파되어 전파된 셀이 된다. B3은 전파된 셀인 A3을 참조하므로 B3도 전파된 셀이 된다.

위 과정이 모두 끝난 뒤에는 셀 병합이라는 기능이 추가로 적용된다. 셀 병합은 다음 조건을 만족할 때 일어난다.

• 1. 순환 참조를 이루는 셀들의 구성이 완전한 직사각형 형태여야 한다. 완전한 직사각형이란 연속된 가로와 세로의 직사각형을 골랐을 때, 내부의 모든 셀이 하나의 순환 참조를 이루는 경우를 말한다.
• 2. 순환 참조를 이루는 모든 셀이 병합에 참여해야 한다.
• 3. 1, 2번 조건을 모두 만족하면 셀 병합은 자동으로 일어난다.
• 4. 병합이 끝나면 병합된 셀은 한 칸으로 합쳐지고, 그 칸의 좌표는 병합에 참여한 셀 중 가장 왼쪽 위 셀의 좌표가 된다.

병합이 끝난 뒤 직사각형을 이루던 모든 셀이 유효하지 않은 셀을 참조하지 않으면, 병합된 셀은 유효한 셀이 된다. 직사각형을 이룬 셀 중 하나라도 유효하지 않은 셀을 참조하면, 병합된 셀은 여전히 유효하지 않은 상태다. 병합으로 유효한 셀이 되는 과정도 연쇄적으로 일어난다. 다만 순환 참조를 직접 이루고 있는 셀에게는 전파되지 않는다.

<그림 2>

<그림 2>에서 A1, B1, A2, B2는 처음에 순환 참조를 이루고 있고, A3은 A2를 참조하므로 전파된 셀이었다. 그런데 A1, B1, A2, B2가 병합되어 하나의 셀 A1이 된다. 병합 전에 이 네 셀 중 유효하지 않은 셀을 참조하는 셀이 없었으므로 병합된 셀은 유효한 셀이 된다. 이를 참조하던 A3도 유효한 셀이 되고, 연쇄적으로 B3도 유효한 셀이 된다.

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

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

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

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

셀의 좌표는 알파벳 대문자 한 글자 또는 두 글자와 1 이상 999 이하의 정수가 결합한 형태다. 가장 왼쪽 위 셀은 A1, 가장 왼쪽 아래 셀은 A999, 가장 오른쪽 위 셀은 ZZ1, 가장 오른쪽 아래 셀은 ZZ999다(힌트의 <그림 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]이 된다.