元の画像での「色」を頂点とみなし、元の画像で隣接している色どうしの間に辺を張ったグラフが「二部グラフ」であるかを判定する問題に帰着できます。 「二部グラフ」とは頂点を2つのグループに分け、同じグループ内のどの2点を取っても隣接していないようにできるグラフのことです。 これは、ある頂点を白く塗り、隣接する頂点を黒く塗り、という操作を繰り返して、矛盾が生じないようにすべての頂点を塗り終われることと同値で、 これこそが題意の「白黒印刷」に対応しています。
具体的な操作としては、上記をそのまま幅優先探索や深さ優先探索を用いて実装することで解くことが出来ます。この時、頂点数は最大ですが、 辺の数は高々程度で抑えられるため、計算量も問題ありません。
また、想定される誤答としては、グラフへの変換を行わずに格子上で、上記のような幅優先探索を行う解法が考えられます。このような操作は、 「同じ色がひとかたまりの連結なマスを除いて別の場所で現れない」のであれば正しいですが、例えば
入力
1 4 3 1 2 3 1
のような場合に「同じ色を違う色で塗り分けてしまう」可能性があり、正確な判定とは言えません。